프로그래머스 [Lv. 2] 다음 큰 숫자 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12911?language=javascript

프로그래머스

정답 코드

function solution(n) {
    let c = n;
    let c0 = 0;
    let c1 = 0;
    
    while ((c & 1) == 0 && (c != 0)) {
        c0++;
        c >>= 1;
    }
    
    while ((c & 1) == 1) {
        c1++;
        c >>= 1;
    }
    
    if (c0 + c1 == 31 || c0 + c1 == 0) {
        return -1;
    }
    
    let p = c0 + c1;
    
    n |= (1 << p);
    n &= ~((1 << p) - 1);
    n |= (1 << (c1 - 1)) - 1;
    
    return n;
}

풀이 방법

1. 오른쪽에서 0의 개수(c0)와 1의 개수(c1) 찾기
   
   1. 먼저, 주어진 숫자의 오른쪽에서 0의 개수와 1의 개수를 찾는다.
      1. c0은 오른쪽에서 연속된 0의 개수이다.
      2. c1은 그 다음에 오는 연속된 1의 개수이다.
      3. 비트 연산 c & 1은 숫자의 가장 오른쪽 비트가 0인지 1인지를 확인한다.
      4. c >>= 1은 숫자를 오른쪽으로 한 비트씩 이동시킨다.
         1. 예를 들어 n이 13948 이진수로 11011001111100인 경우
            1. c0은 2 : 00 부분
            2. c1은 4 : 1111 부분
2. 다음 큰 숫자를 만들기 위한 비트 위치 계산
   1. 다음으로, 다음 큰 숫자를 만들기 위해 필요한 비트 위치를 계산한다.
      1. c0 + c1 == 31 혹은 c0 + c1 == 0인 경우는 다음 큰 숫자가 존재하지 않는 경우이다. 31은 32비트 정수의 모든 비트가 1인 경우를 의미한다.
      2. p는 0과 1의 연속된 길이를 의미한다. 이 위치에서 비트를 변경할 예정이다.
3. 다음 큰 숫자 생성
   1. n의 다음 큰 숫자를 만든다.
      1. n |= (1 << p)는 p 위치의 비트를 1로 설정한다.
      2. n &= ~((1 << p) - 1)는 p 위치의 오른쪽 모든 비트를 0으로 설정한다.
      3. n |= (1 << (c1 - 1)) - 1는 오른쪽에 c1 - 1개의 1을 추가한다.
         1. 예를 들어 n이 13948dls ruddn
            1. p는 6
            2. n |= (1 << 6)는 비트 6을 1로 설정하여 14016 (11011010000000)을 만든다.
            3. n &= ~((1 << 6) - 1)는 6번째 비트 이하를 모두 0으로 만들어 14016을 유지한다.
            4. n |= (1 << 3) - 1는 오른쪽에 3개의 1을 추가하여 최종적으로 14023 (11011010000111)을 만든다.

느낀점

• 무조건 다시 풀어봐야 하는 문제.