3.1프로그래머스 Lv.2 #1~10

개요

프로그래머스에 자바스크립트로 풀 수 있는 Lv.2 문제는 총 113문제가 있다. 정답률 높은 문제 순, 1 ~ 10번 문제 풀이 중 배울 점이 있는 풀이들 또는 고심해서 푼 문제들에서 기억하고 싶은 개념들을 완전히 내 것으로 만들고자 정리해본다.

5. 이진 변환 반복하기

이진 변환 반복하기는 0과 1로 이루어진 문자열 x에 대해

1. 0을 모두 제거하기
2. 그렇게 0이 제거된 x의 길이를 c라고 하면, x를 c를 2진법으로 표현한 문자열로 바꿈.
3. 이 과정을 s가 "1"이 될때까지 반복하고, [이진 변환 횟수, 제거된 모든 0의 개수]를 반환

하는 함수를 작성하는 문제다. 나는 이진 변환 횟수와 제거된 모든 0의 개수를 각각 세는 변수를 만들고, 0을 제거하는 함수를 만들어 루프를 실행했다.

javascript
function solution(s) {
    let counter = 0, removed0 = 0;
    let string = s;
    function remove0(str){
        removed0 += str.match(/0/g)?.length || 0;
        string = str.replaceAll(/0/g, "").length.toString(2);
    }
    while(true){
        remove0(string);
        counter++;
        if(string === "1") break;
    }
    return [counter, removed0];
}

5-1. 개선(리팩토링)

우선 헬퍼(보조) 함수가 바깥에 있는 string이란 변수를 직접 바꾸고 있는데, 결과를 반환하고 바깥에서 해당 변수가 반환된 결과를 할당받는 식으로 작성하는게 좋다. 예를 들어 아래와 같다.

javascript
function remove0(str) {
  const zeros = str.match(/0/g)?.length || 0;
  removed0 += zeros;
  return str.replaceAll("0", "").length.toString(2); // 입력값을 변형해 반환
}

while (string !== "1") {
  string = remove0(string); // 변형해 반환된 값을 원본 변수에 할당
  counter++;
}

또, replaceAll()은 문자열 전체를 새로 만들기 때문에 문자열 길이가 15만까지 될 수 있는 본문제에는 다소 부담스럽다. 마침 0의 개수를 어차피 구하고 있으니, 전체 길이에서 0의 개수를 뺀 것이 1의 개수라고 보면 된다. 따라서 아래와 같이 코드를 개선할 수 있다:

javascript
function solution(s) {
  let counter = 0, removed0 = 0;
  let string = s;

  while (string !== "1") {
    const zeros = (string.match(/0/g)?.length) || 0;
    removed0 += zeros;
    string = (string.length - zeros).toString(2);
    counter++;
  }
  return [counter, removed0];
}

5-2. 재귀

문제에서도 볼 수 있듯이, 이 문제는 재귀 로직으로도 풀 수 있다.

• 기저 조건: 문자열이 "1"이면 [변환 횟수, 제거한 0의 개수]를 반환한다.
• 아니라면, 0을 세고, 남은 1의 개수를 2진법으로 변환하고, 카운트를 1 올리고 재귀를 호출한다.

javascript
function solution(s) {
  function helper(str, count, removed) {
    if (str === "1") return [count, removed];

    const zeros = str.match(/0/g)?.length || 0;
    removed += zeros;

    const next = str.replace(/0/g, "").length.toString(2);

    return helper(next, count + 1, removed);
  }

  return helper(s, 0, 0);
}

6. 숫자의 표현

숫자의 표현은 자연수 n을 연속된 자연수로 표현할 수 있는 방법이 총 몇개인지 구하는 문제다. 예를 들어, 15는 1 + 2 + ... + 5, 4 + 5 + 6, 7 + 8 그리고 15로 서로 다른 4가지 방법으로 표현이 가능하다.

나는 처음에 이렇게 풀었으나, 효율성 측면에서 시간 초과를 받았다. 이런 중첩 for문으로도 통과할거였으면 lv.2가 아니었을 것이다.

javascript
function solution(n) {
    let count = 1; // 자기 자신
    let sum = 0;
    for(let i = 1; i <= Math.floor(n / 2); i++){
        sum = i;
        for(let j = i + 1; j <= Math.ceil(n / 2); j++){
            sum += j
            if(sum === n){
                count++;
                sum = 0;
                break;
               }
            if(sum > n){
                sum = 0;
                break;
            }
        }
    }
    return count;
}

이전에 배운 Sliding Window가 생각나 도입했고, 이걸로 풀 수 있었다. 연속된 자연수의 합이므로 윈도우에 right를 추가하다가, 합계가 n을 넘으면 left를 빼고 left를 한칸 오른쪽으로 당기는 방식이다. 이렇게 풀 경우 O(n)의 시간 복잡도를 가진다.

javascript
function solution(n) {
  let count = 0;
  let sum = 0;
  let left = 1;

  for (let right = 1; right <= n; right++) {
    sum += right;              
    while (sum > n) {
      sum -= left;
      left++;
    }
    if (sum === n) count++;
  }
  return count;
}

6-1. 수학적 성질 이용하기

풀이들 중에 수학적 성질을 이용한 풀이가 있었는데, 막연하게 "나는 못 생각하겠지"라고 생각하고 넘어가기보단 그래도 이번 기회에 알아보자는 마음으로 가져온다.

여기서 쓰는 수학적 성질은 "n을 연속된 자연수의 합으로 나타내는 방법의 수는 n의 홀수 약수의 개수와 같다"는 것이다.

왜냐면 자연수 a부터 시작해 m만큼 연속된 자연수의 합은 a + (a + 1) + (a + 2) + ... (a + m -1)이고, 이는 m * (a + (a + m - 1))/ 2다.(가우스)

즉, n = m * (2a + m - 1) / 2이고, 2를 양변에 곱하면 2n = m * (2a + m - 1)이다. 즉, m이 2n의 약수일때 a부터 시작해 m만큼 연속된 자연수의 합으로 n을 표현할 수 있다는 것이다.

이 때 m이 홀수라면 2a + m - 1 은 짝수일 것이고 짝수 / 2는 자연수이니 n = m * 자연수가 된다. 즉, m이 n의 홀수인 약수일 때 연속합으로 n을 만들 수 있는 경우가 하나 생긴다는 의미다.

m이 짝수여도 마찬가지다. 이땐 2a + m - 1이 홀수일 것이고 m이 짝수이면 n = (m / 2) * 홀수, 즉 n = 짝수의 절반 * 홀수가 되어 결국은 n의 홀수 약수 조건과 같아진다.

정리하면, m이 홀수일땐 n이 m의 배수이면 가능하다는 얘기이니 홀수 약수마다 한번씩 가능하다는 의미가 된다. 또, m이 짝수일땐 n이 m/2 * 홀수 꼴일때만 연속합으로 표현이 가능하다는 얘기이니 마찬가지로 n의 홀수 약수 개수와 1:1로 연속합 종류가 대응한다.

설명이 길었는데, 코드는 짧다:

javascript
function solution(n) {
  let answer = 0;
  for(let i = 1; i <= n; i++){
    if((num % i === 0) && (i % 2) === 1){
      answer++;
    }
  }
  return answer;
}

7. 다음 큰 숫자

이 문제는 어떤 자연수 n이 주어졌을때(100만 이하), n보다 더 크면서 2진수로 변환했을 때 1의 갯수가 같은 가장 작은 수를 10진법으로 반환하라는 문제다.

나는 아주 평범하게 n을 이진법으로 바꾸고, 1의 개수를 세고, 변수 하나를 만들어 1씩 올리면서 1의 개수가 같아지면 그 수를 반환하는 식으로 풀었다:

javascript
function solution(n) {
    const binary = n.toString(2);
    const num1 = binary.match(/1/g).length;
    let comparison = n + 1;
    while(true){
        let num1Comp = comparison.toString(2).match(/1/g).length;
        if(num1 === num1Comp) break;
        comparison++;
    }
    return comparison;
}

7-1. 커니핸(popcount) 알고리즘

이 블로그에서 정리했던 Understanding the Digital World의 저자 브라이언 커니핸님이 1비트 개수를 빠르게 세는 알고리즘을 만들었다고 한다. 핵심 아이디어는:

x &= (x - 1) 연산을 할 때마다 가장 오른쪽(RSB) 1비트가 하나씩 지워진다는 원리로, 이걸 0이 될때까지 반복하면 반복 횟수가 1의 개수다.

이게 무슨 말일까? 예를 들어 아래의 사례를 살펴보자. 임의의 양의 정수 x를 이진수로 쓸 때, 어쨌든 가장 오른쪽에 있는 1이 있을 것이다(2^0의 자리건, 2^1의 자리건, ... 아무튼 수 자체가 0이 아닌 이상 1이 반드시 포함되어 있다).

그러면 x - 1은 그 1이 있는 자리는 0이고 바로 그 아랫자리수는 모두 1일 것이다. 즉, 아래와 같다.

bash
x      = ... 1 0 0 0 ... 0
x - 1  = ... 0 1 1 1 ... 1

이 둘을 & 연산하면 맨 오른쪽 1을 포함해 그 아래는 모두 사라지고 그보다 왼쪽 비트들은 그대로 유지된다. 즉, 해당 비트수에서 1을 하나 없앨 수 있는 것이다.

따라서 이 연산을 x의 모든 자릿수가 0이 될때까지 반복하고, 몇번 했는지 따져보면 1의 개수를 셀 수 있다. 이 방식은 시간 복잡도가 O(k)로, k는 1의 개수다. 이 방식은 배열로 훑는 단순 시프트 방식보다 대부분 훨씬 빠르다.

이 알고리즘은 자바스크립트에선 아래와 같이 구현할 수 있다. 단, 정수가 매우 크면 BigInt로 정의해야할 것이다.

javascript
function popcount(x) {
  let c = 0;
  while (x) {
    x &= (x - 1);
    c++;
  }
  return c;
}

이 함수를 사용하면 이 문제는 아래와 같이 더 간단하게 풀 수 있다:

javascript
function popcount(x){
  let c = 0;
  while(x) {
    x &= (x - 1);
    c++;
  }
  return c;
}

function solution(n){
  const target = popcount(n);
  let x = n + 1;
  while(popcount(x) !== target) x++;
  return x;
}

7-2. 재귀

n이 100만 이하이므로 스택 오버플로우가 날 수도 있다는 한계가 있지만, 재귀로 연습해보는것도 가치가 있다고 생각한다. 성능은 사실 그다지 좋지 않지만, 재귀로 생각해볼 수 있다는 것에 가치가 있다.

javascript
function solution(n, a = n + 1){
  return n.toString(2).match(/1/g).length ===
    a.toString(2).match(/1/g).length ? a : solution(n, a + 1);
}

7-3. 내 풀이와 같은 원리, 좀 더 간결한 코드

이런 풀이도 있었다. 개인적으로 while문 안에 n++는 쓸 때 익숙하지 않지만 아래의 코드가 더 읽기 쉽고 간편하다는 것은 반박할 수 없다.

javascript
function nextBigNumber(n) {
    const size = n.toString(2).match(/1/g).length
    while(n++) {
        if(size === n.toString(2).match(/1/g).length) return n
    }
}

8. 짝지어 제거하기

짝지어 제거하기는 전형적인 스택 문제다. 알파벳 소문자로 이루어진 문자열이, 연속으로 붙은 문자가 있으면 제거하는 로직을 계속 실행했을 때 완전히 문자를 없앨 수 있다면 1을, 없다면 0을 반환하는 함수를 작성해야 한다.

스택을 만들고, 문자열을 순회하며 스택에 쌓고 만약 다음에 쌓으려는 문자가 스택의 맨 끝에 있으면 스택을 터뜨리는 식으로 진행해 최종 스택 길이를 확인하는 식으로 풀었다.

javascript
function solution(s){
  if(s.length % 2 !== 0) return 0; // 홀수 개수면 불가능
    
  const stack = [];
  for(let i = 0; i < s.length; i++){
      const ch = s[i];
      if(stack.length && stack[stack.length - 1] === ch){
          stack.pop();
      } else {
          stack.push(ch);
      }
    }
  return stack.length === 0 ? 1 : 0;
}

9. 피보나치 수

피보나치 수는 얼핏 봣을땐 굉장히 쉬운 재귀 문제인것 같지만, 제한 사항이 n이 100,000까지 갈 수 있기 때문에 재귀로 풀면 스택 오버플로우가 나는 문제다.

예를 들어, 아래의 풀이는 시간 초과된다.

javascript
function solution(n) {
    function fibonacci(num){
        if(num === 0) return 0;
        if(num === 1) return 1;
        return (fibonacci(num - 1)) + fibonacci(num - 2);
    }
    return fibonacci(n) % 1234567;
}

따라서 이 문제는 동적 계획법(Dynamic Programming)으로 풀어야한다.

9-1. 반복문(Dynamic Programming, Bottom-up)

DP의 Bottom-up 방식은 반복문으로 작은 문제부터 차례대로 채워나가는 방식이다. 지금하고 있는 모듈러(%) 연산은 덧셈에 대한 분배법칙이 성립한다. 즉, (A + B)를 m으로 나눈 나머지는 각자를 m으로 나눈 나머지들의 합을 m으로 나눈 나머지와 같다.

이 원리를 사용하면 아래와 같이 피보나치 수를 직접 구하면서 커지기 전에 나머지를 더하는 식으로 구할 수 있다.

javascript
function solution(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    const next = (a + b) % 1234567;
    a = b;
    b = next;
  }
  return b;
}

9-2. 배열 DP

피보나치 수를 모두 배열에 저장하면서 구하는 것도 방법이다. 물론, 이 때도 모듈러의 덧셈에 대한 분배법칙 원리를 적용한 상태로 푼다. 그렇지 않으면 BigInt를 모두 적용해서 풀 수도 있는데, BigInt는 숫자보다 연산이 느리기 때문에 성능을 위해서라면 권장하진 않는다.

javascript
function solution(n) {
  const dp = Array(n + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;

  for (let i = 2; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
  }
  return dp[n];
}

10. 카펫

카펫은 아래와 같은 형태로 가로가 더 긴 갈색/노란색 카펫이 있을 때, 갈색/노란색 격자의 개수가 주어지면 전체 카펫의 가로, 세로 길이를 반환하는 문제다.

나는 갈색은 반드시 4개의 꼭지점을 가지고, 꼭지점을 제외하면 윗변과 아랫변은 노란색의 가로 길이, 좌변과 우변은 노란색의 세로 길이라는 점을 이용해 공식을 세웠다. 노란색의 높이는 가로보다 작으면서 노란색 전체의 개수를 나누어 떨어지게 나누니, for문으로 순회하며 갈색 수를 만족시키는 노란색의 세로와 가로를 구하고 이걸 토대로 전체 카펫의 가로, 세로를 반환했다.

javascript
function solution(brown, yellow) {
    let yellowWidth = 0, yellowHeight = 0;
    for(let h = 1; h <= Math.sqrt(yellow) ; h++){
        let tempWidth = 0, tempHeight = 0;
        if(yellow % h === 0){
            tempHeight = h;
            tempWidth = yellow / h;
            if(brown - 4 === tempHeight * 2 + tempWidth * 2){
                yellowHeight = tempHeight;
                yellowWidth = tempWidth;
                break;
            }
        }
    }
    return [yellowWidth + 2, yellowHeight + 2];
}

10-1. 개선(리팩토링)

이 풀이는 여러 방면으로 리팩토링이 가능한데, 주로 필요없는 변수 할당을 정리하는 것이다. 위의 풀이에서 temp~와 yellow~는 사실 구분할 필요가 없다. 조건을 만족시킬때 반환하면 되지만, 그렇지 못할땐 그냥 다음 루프에서 재할당하면 된다.

또, 최종 관심이 있는건 전체 너비와 길이인데, 전체 너비와 길이를 곱하면 brown과 yellow를 더하는 것과 같게 되어야한다는 점을 조건으로 이용한다.

javascript
function solution(brown, yellow) {
  for (let h = 1; h <= Math.sqrt(yellow); h++) {
    if (yellow % h === 0) {
      const w = yellow / h;  // 노란색 가로
      const totalW = w + 2;
      const totalH = h + 2;
      if (totalW * totalH === brown + yellow) {
        return [totalW, totalH];
      }
    }
  }
}

10-2. 거꾸로 풀기

yellow의 가로 세로를 구하는 방식으로 풀어도 되지만, 반대로 yellow의 개수를 만족시키는 전체 가로 세로를 구하는 방식으로도 풀 수 있다. 전체 면적의 약수 쌍 중에서 내부 영역이 정확히 yellow인 것을 찾으면 된다.

성능적으론 아무래도 yellow의 수가 total의 수보단 작을수밖에 없으니 앞선 풀이인 yellow의 가로 세로를 구하는 방법이 나을 수 있으나, 아래 풀이는 구하고자 하는 전체의 너비와 높이를 직접 구해서 가독성이 좋다.

javascript
function solution(brown, yellow) {
  const total = brown + yellow;

  for (let h = 3; h <= Math.sqrt(total); h++) {
    if (total % h === 0) {
      const w = total / h;
      if ((w - 2) * (h - 2) === yellow) {
        return [w, h];
      }
    }
  }
}