[항해99][2주차] #0. JS 알고리즘 마라톤

Hajun Song·2022년 6월 24일
0

항해99

목록 보기
6/8
post-thumbnail

[2주차] #0. JS 알고리즘 마라톤

항해99의 2주차. 정확히 말하자면 1주차의 미니 프로젝트가 끝난 직후 금요일부터 알고리즘 마라톤 주간이 시작되었다. 알고리즘 마라톤은 걷기반달리기반으로 구성되어 있고 1주일 동안 조원끼리 28문제(달리기반은 40문제) +@의 프로그래머스 문제를 풀고 그 중 문제를 나눠 맡아서 서로에게 설명하는 스터디 주간이다.

많은 이들에게 주특기 시작 전 베이스 언어 숙달 과정이 되지 않을까 싶다.


  • 달리다 넘어진 애기가 더 잘 걷겠지!
  • 빨리 달리는 자전거가 느린 자전거 보다 덜 넘어진다! 딴생각 할 틈 없이!

이런 마음으로 했던 선택인지라 조원들과 함께한다는 말을 듣고는 팀 팀원들 템포에 따라 갈 수 있을지 걱정이 되었다. 개인 플레이인줄 알았던 것이 잘못인 걸까. 모자란 실력으로 달리기반에 들어온 잘못인 걸까.

우선 알고리즘 마라톤 기간 동안 JS에 대한 개념이 부족한 만큼 알고리즘 해결능력 중심의 성장 보다는 생소한 언어의 기본적인 기능 숙달을 목표로 정하고 2주차 시작에 임했다.


양식

아래는 달리기반의 40문제 중 내가 설명을 맡은 문제나 그와 함께 배운 개념 정리이다.
양식은 아래와 같다.


문제 이름

여기는 문제 설명을 요약해둔 자리입니다. 자세한 내용은 링크를 참고하세요.
문제 풀이의 제한사항을 요약해둔 자리입니다. 자세한 내용은 링크를 참고하세요.

  • 1번 풀이 방법
<h1>hello,world!</h1>

배우게 된 메서드 or 해결 방식

배우게 된 메서드 또는 방식의 예시를 간략히 적었습니다.

💖참고하면 좋을만한 장점과 예시를 간략히 적었습니다.

💡 참고하면 좋을만한 변화형들과 예시를 간략히 적었습니다.

응용하면 좋을만한 사용방법과 예시를 간략히 적었습니다.

오류와 해결에 사용 한 해결방법을 간략히 적었습니다


프로그래머스

1. 수박수박수~

길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요.
n은 길이 10,000이하인 자연수입니다.

  • 1번 풀이 방법
function solution(n) {
    var answer = '';
    for (i=1;i<n+1;i++) {                 //i가 n번 반복할 때 까지
        if (i%2==1) {                     //i가 홀수면
            answer=answer+'수'            //문자열에 '수' 붙이기
        }
        else {                            //i가 짝수면 '박'
            answer=answer+'박'            //문자열에 '박' 붙이기
        } 
    }
	return answer
}
  • 2번 풀이 방법
function solution(n) {
    var answer = '';
    

    let watermelon='수박'
    answer=		//글자의 길이가 n이고 수박은 2글자이므로 'n/2'번 만큼 수박을 붙이기
        answer+'수박'.repeat(n/2)
    if (n%2==1) {                           //남은 n이 1개면
        answer=
            answer + '수'                   //문자열에 '수' 붙이기
    }
	return answer
}
  • 3번 풀이 방법
function solution(n) {
    return '수박'.repeat(5000).substring(0,n);	//5000개의 수박중 원하는 만큼 가져가
}

문자열 자르기 substring(int begin_index,int end_index)

string을 자르는데 사용한다. string.substring(int begin_index,int end_index)
index를 포함한 문자를 리턴한다.
ex) '무지개가무지무지이쁘다'.substring(4,7) 결과: 무지무지

💖 end_indexbegin_index보다 크더라도 알아서 바꾸어 오류없이 작동한다.
ex) '무지개가무지무지이쁘다'.substring(2,0) 결과: 무지개

💖 end_index가 string의 길이보다 크더라도 알아서 길이만큼 오류없이 작동한다.
ex) '무지개가무지무지이쁘다'.substring(4,999) 결과: 무지무지이쁘다

💡 필요에 따라 end_index를 사용하지 않을 수도 있다.
string.substring(index)를 이용하면 index를 포함한 이후 문자를 전부 리턴한다.
ex) '무지개가무지무지이쁘다'.substring(4) 결과: 무지무지이쁘다

substring()length를 함께 사용하면 string의 길이를 몰라도 문자열의 마지막 글자들을 가져 올 수 있다.

ex) let exstring = 'https://www.youtube.com/watch?v=D5YijJqhvgA'
	let videoCode = exstring.substring(exstring.length - 11)
	console.log(videoCode) // 결과 : D5YijJqhvgA

2. 자릿수 더하기

자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.
N의 범위는 100,000,000 이하의 자연수입니다.

  • 1번 풀이 방법
function solution(n){
  var answer = 0;
  arry=String(n).split('')                //숫자를 문자형으로 변환 후 자릿수 단위로 split
  for (i=0;i<arry.length;i++) {           //자릿수 만큼 반복하는 for
      answer= answer+parseInt(arry[i])    //문자를 숫자로 변환 후 더하기
  }
  return answer;
}

자료형 변환 String() / parseInt()

String은 숫자를 문자로 변환하기 위해사용하고, 대문자 S
parseInt는 문자를 정수형 숫자로 변환하기 위해 사용한다. 대문자 I

💡parseFloat은 문자를 실수형 숫자로 변환해준다.

parseInt는 사실 문자만 정수형 숫자로 변환하는 것이 아니다. 문자가 아닌 실수에 사용하여도 정수로 변환해준다. 이를 이용해 소숫점 이하의 수를 버릴 수 있다.
ex)console.log(parseInt(33.624476651)) 결과: 33


3. 정수 제곱근 판별

임의의 양의 정수 n에 대해 n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요.
n은 1이상, 50000000000000 이하인 양의 정수입니다.

  • 1번 풀이 방법
  function solution(n) {
    return (Math.sqrt(n)%1==0 ? (Math.sqrt(n)+1)**2 : -1)}
  //n이 양의 정수 x의 제곱인가? == n의 제곱근은 양의 정수인가? ?
  //그렇다면 n의 제곱근에 1을 더하여 제곱한 값을 : 아니면 -1을 리턴하라.
  • 멍청했던 실수

진짜 정말 멍청하게 문제를 읽었다. 임의의 수 n이 양의 정수 x의 제곱이다. 이때, x를 찾아 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는... 결국 반만 읽고 생명물리에서 다루던 이진검색인줄 알고 한시간 반 동안 뻘짓했다. 물론 그 후 질문을 다시 읽고 위의 코드로 바로 성공했다.

🐱‍💻Note

문제를 잘 읽자.

//당연한 시간초과 코드. 멍청이는 n을 받은줄도 모르고 직접 찾아야 해야하는 줄 알았다.
  
function solution(n) {
    var answer = 0;
    let maximum = 50000000000000;	// 기계는 우직해야해!!
    for (i=0; i<maximum; i++) {		// 50000000000000번 연산해봐
        if (i*i==n) {
            return (i+1)*(i+1)
        }
    }
    return -1
  
} 
//멍청이 2는 그 중에eh 검색 방법을 효율적으로 해서 시간을 줄여보자!
function solution(n) {
    var answer = 0;
    let maximum = 49999988518489;
                  
    for (i=0; i<47; i++) {
        if (n<=maximum/(2**i)) {
            console.log(maximum/(2**i),'보다는 작거나 같습니다.')
            }    
        else {console.log(maximum/(2**i),'보다 큽니다. 그 사이를 찾습니다.')
              
              for (t=parseInt(maximum/(2**i));t<maximum/(2**(i-1));t++) {
                  if (n==t && Math.sqrt(t)%1!=0) {
                      console.log('찾았다!','하지만 바라던게 아니었다...')
                          return -1
                      }
                  if (n==t){
                      console.log('찾았다!',n)
                      return((Math.sqrt(t)+1)**2 )
                      
                  }        
                  
              } 
        }
    }
}
//정말 허술한 이진탐색이었다.

삼항연산자 condition ? exprIfTrue : exprIfFalse

삼항 [조건문condition, 참일 때 실행할 식exprIfTrue, 거짓일 때 실행할 식exprIfFalse] 을 이용해 세개의 피 연산자를 이용할 수 있는 방법이다.
ex)

function solution(n) {
    return (n%2===0 ? '짝수' : '홀수' )}
    	  //n은 짝수 ?
    		  //참이면 '짝수' :
					 //:아니면 '홀수' 

💖아직 익숙하지는 않지만 if 명령문의 단축 형태로 사용하기에 딱 좋다. 머리 아프게 else를 안써도 된다는 장점도 크고 알고리즘 답안 제출할 때 짧고 이쁘다.


4. 하샤드 수

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.
x는 1 이상, 10000 이하인 정수입니다.

  • 1번 풀이 방법
function solution(x) {
    var answer = true;
    let y=x;                //x 가공을 위한 클론 y
    let digit=0;            //자릿수의 합
    
    for (i=0; i<5 ;i++) {
        if (y != 0) {
            digit+= y % 10          //10으로 나눈 나머지(1의 자릿수)
            y=Math.floor(y/10)      //10으로 나눈 후 정수 추출
        }
        else {
            if (x % digit != 0) {   
                answer = false;}
            return answer;
        }
    }  
}

🐱‍💻Note

자료형 변환을 최소화 하자


5. 같은 숫자는 싫어

배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.
배열 arr의 크기 : 1,000,000 이하의 자연수

  • 1번 풀이 방법
function solution(arr) {
    var answer = [];

    for (i=0; i<arr.length;i++){
        if (arr[i]!=arr[i-1]) {
            answer.push(arr[i])
        }
    }
    return answer;
}
  • 2번 풀이 방법
function solution(arr){
    return arr.filter((val,index) => val != arr[index+1]);
}

필터 Array.filter()

filter함수를 이용해 배열로부터 필터링된 값들만 보여주는 기능이다. 3개의 매개변수 (, 인덱스, 배열)을 이용하며 true, false로 값을 도출하는 함수가 필요하다.

//ex)
var arr = [{ id: 15 },{ id: -1 },{ id: 0 },{ id: 3 },{ id: 12.2 }]

function filterByID(item) {
  if (item.id !== 0) {
    return true;
  }
  return false;
}

var arrByID = arr.filter(filterByID);
//0. arr[0]부터 가져온 값을 순차적으로 함수에 넣는다.
//1. true가 나오면 저장, false가 나오면 버려진다.
//2. 이때 배열 arr 자체는 변하지 않는다.
console.log(arrByID)
//결과 : [{ id: 15 }, { id: -1 }, { id: 3 }, { id: 12.2 }]

화살표 함수 () =>

화살표 함수는 기본 함수식에서 function과 내용을 가두는 {} 그리고 결과값 도출을 위한 return을 안적어도 되는 함수 표기법이다. 함수가 필요한 기능들에 넣어 (매개변수) => 식의 표현으로 짧게 표현하기에 용이하다.

//ex) 위와 같은 예제
var arrByID = arr.filter((item) => item.id!==0);
// (item) => item.id!==0  ------> true ----> filter
// 결과 : [{ id: 15 }, { id: -1 }, { id: 3 }, { id: 12.2 }]

💖 삼항연산자처럼 짧고 조아..


6. 시저 암호

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요.
공백은 아무리 밀어도 공백입니다. n은 1 이상, 25이하인 자연수입니다.

  • 1번 풀이 방법
function Exercise_12926(s, n) {
        var answer = '';
  		//s 전체 길이 s만큼 반복한다
        for(i=0;i<s.length;i++) {
          //s의 i번째 요소가 띄어쓰기일때 띄어쓰기는 그대로 반환
            if (s.charCodeAt(i)==32){	
                answer+=' '
            }//s의 i번째 요소가 대문자일때(65~90)
            else if (s.charCodeAt(i)>=65 && s.charCodeAt(i)<=90) {	
              //시저암호화의 결과가 Z를 넘어 대문자 구간을 넘으면
                if (s.charCodeAt(i)+n >=91) {
                  //-26를 통해 다시 구간 안으로
                    answer+=String.fromCharCode(s.charCodeAt(i)+n-26)           
                }
                else {//대문자 구간 안에 있으면 반환
                    answer+=String.fromCharCode(s.charCodeAt(i)+n)      
                }
            }//s의 i번째 요소가 소문자일때(97~122)
            else if (s.charCodeAt(i)>=97 && s.charCodeAt(i)<=122) {  
              //시저암호화의 결과가 z를 넘어 소문자 구간을 넘으면
                if (s.charCodeAt(i)+n >=123) {  
                  //-26을 통해 다시 구간 안으로
                    answer+=String.fromCharCode(s.charCodeAt(i)+n-26)
                }
                else {//소문자 구간 안에 있으면 반환
                    answer+=String.fromCharCode(s.charCodeAt(i)+n)          
                }
            }
        }
        return answer;
    }
  • 2번 풀이 방법
function Exercise_12926_sub(s, n) {
        var answer = '';
        for(i=0;i<s.length;i++) {		//s 전체 길이에 대하여
            let ascii = s.charCodeAt(i)	//ascii는 s의 i번째 요소의 아스키코드
            if (ascii==32){answer+=' '}	//ascii가 띄어쓰기(32)면 그대로 반환
            else if (ascii>=65 && ascii<=90) {	//s의 i번째 요소가 대문자일때(65~90)
                answer+= ascii+n >=91 ?       	//시저암호의 결과가 대문자 구간을 넘어가는가?
                          String.fromCharCode(ascii+n-26) : String.fromCharCode(ascii+n) }
        						//true:-26을 통해 대문자 구간 내로 복귀 후 재변환,
          											//false: 그대로 변환
            else if (ascii>=97 && ascii<=122) {	//s의 i번째 요소가 소문자일때(97~122)
                answer+= ascii+n >=123 ?
                          String.fromCharCode(ascii+n-26) : String.fromCharCode(ascii+n) }
        }
        return answer;
    }
  • 2번 풀이 방법
function Exercise_12926_map(s, n) {
        var chars = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXY                          "
        return s.split('').map(e => chars[chars.indexOf(e)+n]).join('');
        //s를 배열로 분리, 각각의 값을 indexOf를 이용해 chars에서 첫번째 위치를 가져옴.
        //첫번째 위치에서 +n, n은 25이하인 자연수이므로 알파벳을 1번 더 반복해두면 문제 없음.
        
        //map
        //filter랑 똑같이 3개의 매개변수와 함수를 이용 (필수: 불러온 값,선택: index,선택: 호출한 배열)
        //배열 내의 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환.
    }

배열 지도 map()

map을 촌스럽게 지도로 번역을 했다. 필터와 동일하게 3개의 매개변수(, 인덱스, 배열)를 갖는다. 또 함수도 똑같이 필요하다. 다만 true, fales를 내놓아야 할 필요는 없다. map은 처리할 요소를 순차적으로 함수에 넣고 함수에 의해 도출된 값을 새로운 배열에 담는다.

//ex)
let a = [1,2,3,4,5]
var b = a.map( (val) => val%2==0 ? val-1 : val+3);
// 0. 배열 a로부터 순차적으로 a의 요소 val을 가져와 화살표 함수에 전달한다.
// 1. 삼항연산자에 따라 val을 2로 나눈 나머지가 0이면(짝수이면) ? 이후의 식에 따라 val-1을 반환한다.
// 2. 또, : 이후의 식에 따라 홀수이면 val+3을 새로운 배열 b에 반환한다.
console.log(b)
//결과 : [4,1,6,3,8]

💖 지도만 있으면 못난이 요소들도 각자 가야할 길을 쉽게 갈 수 있거든.. -어린황자-


profile
일단 똥을 싸라, 그리고 박수칠 때 까지 닦아라.

0개의 댓글