[JS] 알고리즘 도전반 1일차 풀이

---

문제 1번

---

12와 18의 약수
12: 1, 2, 3, 4, 6, 12
18: 1, 2, 3, 6, 9, 18

• 최대공약수
  최대공약수를 알기 전, 공약수는 두 수 혹은 그 이상의 여러수의 공통인 약수를 뜻한다.
  최대공약수는 이름 그대로 공약수 중 가장 큰 것을 가리킨다.
  위에 나와있는 12와 18의 약수 중 공통된 수중에 제일 큰 숫자가 최대공약수이고 6이다.

• 유클리드 호제법
  2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
  이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
  -위키위키백과백과

• 풀이방식
  유클리드 호제법과 재귀함수를 이용하여 풀면 쉽게 풀 수 있을 것 같다.

1. a와 b를 입력받는다.
2. a가 b보다 작을 때 구조분해할당을 이용하여 두 변수에 담긴 값을 바꾸어준다.
3. 삼항 연산자를 이용하여 a를 b로 나누었을 때 나머지가 0이면 b를 반환, 0이 아니면 재귀하여 첫번째 인자에 b를 넣어주고 두번째 인자에 a와 b를 나눈 나머지를 넣는다.

• JS코드

const solution = (a,b) => {
  if(a<b) [a,b]=[b,a];
  return a%b === 0 ? b : solution(b,a%b);
}

---

문제 2번

---

• 풀이방식
  해당 문제는 배열의 인자를 하나씩 비교하여 even,odd 변수에 각각 카운트 해주고 리턴해주는 방식으로 풀면 될 것 같다.

1. arr 인자에 배열을 받는다.
2. odd, even 변수를 0으로 선언 및 초기화 한다.
3. forEach 구문을 통해 arr의 요소를 하나씩 꺼낸다.
4. 조건문을 이용하여 2로 나누었을 때 0이면 even을 증감, 1이면 odd를 증감한다.
5. 배열 형태로 리턴한다.

• JS코드

const solution = arr =>{
    let odd = 0, even = 0;

    arr.forEach(e => {
        if (e%2 === 0) {
            even++;
        }else{
            odd++;
        }
        
    });
    return [odd, even];
}

---

문제 3번

---

• JS 문자 아스키코드 변환방법
  1. 문자를 아스키코드로 변환
  "문자".charCodeAt();
  2. 아스키코드를 문자로 변환
  String.fromCharCode(아스키코드);
  

* 풀이방식
문자열을 역순으로 배치하고 알파벳을 하나씩 옮기는 문제로, 하나씩 잘라서 변환하여 넣는 것보다
배열화 시켜서 forEach로 하나씩 오른쪽으로 이동하고 unshift를 통해 다른 배열에 역순으로
넣은 후 join 메서드를 통해 리턴하는 방향으로 생각했다.

1. 문자열을 str인자로 받는다.
2. rtnArr 변수를 배열로 초기화하여 만들어 놓는다.
3. str을 전개연산자를 통해 배열화 시키고 forEach를 사용하여 요소 하나씩 처리한다.
4. 위 문제는 소문자였을경우니까 z의 유니코드 다음은 '{'이기 때문에 z가 아닌경우에만 이동시키고 z인 경우에는 'a'를 반환시킨다.
5. rtnArr 배열에 unshift 하여 변환시킨 요소를 넣는다.
6. 마지막으로 rtnArr.join("");을 리턴시킨다.

• JS코드

const solution = str =>{
    const rtnArr = [];
    [...str].forEach(chr=>{
        if(chr!=='z') rtnArr.unshift(String.fromCharCode(chr.charCodeAt()+1));
        else rtnArr.unshift('a');
    });
    return rtnArr.join("");
}

---

문제 4번

---

• 풀이방식
  배열의 인덱스를 점진적으로 증가시켜서 한바퀴를 돌게 만들면서 탐색시키는 방향으로 생각했다.
  (이게 뭔말;; 국평오 죄송..)

1. 초밥 종류를 담을 Map을 생성한다.
2. 최대 몇종류의 초밥을 먹었는지 알 수 있는 max 변수를 생성하고 초기화한다.
3. 이중 반복문을 만든다. 외부 for문은 arr 인덱스를 돌려줄 용으로 만든다.
4. 내부 for문은 현재 외부 for문 인덱스부터 시작하여 탐색한다. 이때 중복이 나오기 전까지 점진적으로 돌아가며, 마지막 인덱스에 도착했을경우 탐색 인덱스를 0으로 돌린다.
5. 내부 for문에서 중복이 발생했을경우 현재 Map의 사이즈를 max변수와 비교한 후 큰 값을 넣어주고 Map을 초기화해준 후 내부 for문을 중단한다.
6. 최종적으로 외부 for문이 중단되면 전체적으로 탐색이 끝난 후이기에 max를 리턴한다.

• JS코드

const solution = arr => {
    const myMap = new Map();
    let max=0;
  
    for(let i=0; i<arr.length; i++){
      for(let j=i; j<arr.length; j++){
        if(!myMap.has(arr[j])){
          myMap.set(arr[j],0);
        }else{
          max > myMap.size ? max = max : max = myMap.size ;
          myMap.clear();
          break;
        }
        if(j === arr.length-1) j=-1;
      }
    }
    return max;
  }

---

문제 5번

---

• 풀이방식

1. 스택 방식으로 하나씩 넣는다.
2. for문을 이용하여 반복시키고 내부에서 while문을 이용하여 조건에 맞는 값을 제거한다.
3. push 메서드를 이용하여 적재한다.
4. 반복문이 종료되어도 k가 남은경우 뒤에서부터 삭제한다.
5. 배열을 join메서드를 이용하여 문자열로 리턴한다.

• JS코드

const solution = (num,k) => {
    const numArr = [...num];
    let temp = [];
    let remove = k;
  
  for(let i=0; i<numArr.length; i++){
    while(remove>0 && temp.length>0 && temp[temp.length-1]<numArr[i]){
      temp.pop();
      --remove;
    }
    temp.push(numArr[i]);
  }
  
    temp = temp.slice(0, temp.length-remove);
  
  
  return temp.join("");
  }
  
  console.log(solution("1924",2)); // 94

총평

5가지의 문제를 풀어보았는데, 더 많은 시간을 공부에 할당 해야할 것 같다.
알고리즘 , 자료구조에 대해 무지한 상태라 더 효율적인 방법이 있을텐데 활용할 수가 없다.
남들 너무 잘하던데,, 주눅들지 말고 열심히 살자.