Leet Code

Level: Easy

476. Number Complement

보수를 구하는 문제이다.
풀이로는 Input을 2진수로 변환하고 1bit씩 비교하는 것과 Input의 자리수만큼 1로 채우고 빼는 방법이 있다.

// 1. 
var findComplement = function(num) {
    const bin = String(num.toString(2));
    let answer = '';
    for(let i = 0; i < bin.length; i++){
        answer = answer + (bin[i] == '0' ? '1' : '0');
    }
    return parseInt(answer, 2);
};
// 2. 
var findComplement = function(num) {
    const copy = num;
    let sum = 0;
    while(num > 0) {
        sum = (sum << 1) + 1; // 1비트를 주고 1을 더함.
        num >>= 1; // 1비트를 없앰. 
    }
    return sum - copy;
};

느낀 점: 가볍게 넘긴 비트연산자에 대해서 공부를 다시 해야겠다.

1. Two Sum

주어진 배열에서 두 수를 합쳐 target 변수와 같게끔 만드는 문제이다.
풀이로는 선형탐색을 통해 해결하는 방법과 (이 경우 O(n^2)이다.)
해쉬맵을 사용하여 Memorization을 하는 방법이 있다.

// 1. 생략
// 2. 
var twoSum = function(nums, target) {
  const hashMap = new Map();
  for(let i = 0; i < nums.length; i++) {
    // 타겟에서 현재 배열 값을 뺀 값을 저장한다. 
    const memo = target - nums[i];
    // 만약 해시맵에 해당 값이 있다면 두 수를 더한 합이 정답이기 때문에 멈춘다.
    if(hashMap.get(memo) !== undefiend) return [hash.get(find), i];
    // 해시맵에 해당 값이 없기 때문에 해시맵에 추가한다. 
    hash.set(nums[i], i);
  }
  
  return null;
};

느낀점: Memorization이 필요한지 꼭 생각을 해야겠다. 또, 해시맵을 사용하여 풀 수 있는지도 검토해야 한다.

프로그래머스

1단계

실패율(2019 kakao blind recruit)

function solution(N, stages) {
    let answer = [];
    let people = stages.length;
    for(let i = 1; i <= N; i++) {
        let tmp = stages.filter(n => n === i).length;
        answer.push([i, tmp/people])
        people -= tmp;
    }
    answer = answer.sort((a, b) => b[1] - a[1]);
    return answer.map(a => a[0]);
}

스테이지가 1~5단계 순으로 정렬되는 것을 알아야 한다.
따라서 stages 배열에서 1부터 5까지 각 스테이지에 머물러 있는 사람을 구하고 비율을 구한다.
또한 2차원 배열로 만들었기 때문에 sort 함수는 index를 통해 compareFunction을 a-b로 하여 내림차순 정렬 해주고
2차원 배열의 0번째 인덱스를 꺼내서 1차원 배열로 만들어 반환한다.

느낀 점: 해시맵으로 만들어도 될 것 같다! javascript의 sort() 메서드의 compareFunction을 쓰는 법을 알게 되었다.

약수의 개수와 덧셈

function solution(left, right) {
    var answer = 0;
    let divisor;
    for(let i = left; i <= right; i++){
        divisor = 0;
        for(let j = 1; j <= i; j++) {
            if(i % j === 0) {
                divisor++;
            }
        }
        if(divisor % 2 == 1) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}

다른 사람의 풀이

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}

다 풀고나서 다른 사람의 풀이를 봤을 때는 정말 깜짝 놀랐다. 프로그래밍에 수학을 접목한다는 것은 이런거구나! 느낄 수 있었다. 정수론을 다시 공부해야 겠다..

3진법 뒤집기

function solution(n) {
    var answer = '';
    while(n >= 1){
        answer += n%3;
        n = n / 3;
        n = parseInt(n);
    }
    answer = parseInt(answer, 3);
    return answer;
}

리트코드 문제를 풀때 parseInt로 진법변환이 되는 것을 알고 있었는데, while문으로 직접 바꾸면 reverse할 필요가 없다고 생각해 직접 바꾸었고 parseInt로 문자열을 다시 바꾸어주었다.

다른 사람의 코드

const solution = (n) => {
    return parseInt([...n.toString(3)].reverse().join(""), 3);
}

문자열에 spread 연산자를 사용하면 하나씩 나눠지는 것을 배울 수 있었다.