[Programmers] 다음 큰 숫자

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

 

---

 

문제 해결 과정

착안

비트 연산을 활용하여 아래의 과정을 통해 규칙에 따라 주어지는 수 $N$의 다음 숫자를 구하고자 하였다.

 

$N$을 이진법으로 표현하였을 때,

• 가장 오른쪽에서부터 시작하여 왼쪽 방향으로 '01' 비트가 처음 등장하는 부분을 찾는다(아래 코드의 while문).
• 해당 '01' 비트를 10으로 바꾼다(아래 코드의 while문 다음의 코드 두 줄에 해당).
• 해당 '01' 비트보다 오른쪽에 비트 1이 존재하는 경우, 최대한 낮은 자리수로 밀어넣는다.

 

구현

위의 과정들 중 마지막 과정에 해당하는 결과를 얻기 위해, 우선 주어진 수를 이진법으로 표현했을 때 '01' 비트의 위치(아래 코드에서 변수 $i$)를 찾고 해당 비트보다 오른쪽에 비트 1이 몇 개 존재하는지를 파악하였다(아래 코드에서 변수 $ones$).

 

이때 비트 1들을 우측으로 이동시킬 공간이 있는 경우(즉, $i - 1 > ones$ 인 경우), 숫자 1을 $ones$ 만큼 왼쪽 시프트 연산(<<)을 수행한 결과에서 1을 빼면 '01' 비트보다 오른쪽에 있는 비트 1들을 최대한 우측으로 이동시킨 결과를 구할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

int solution(int n)
{
	int answer = n, i = 1, z = 0x01, ones = 0;
	while (true)
	{
		if (n & z)
		{
			if (!(n & z << 1))
				break;

			ones++;
		}

		i++;
		z <<= 1;
	}

	answer += z << 1;
	answer -= z;

	if (ones)
		if (i - 1 > ones)
		{
			answer -= (n % z);
			answer += (0x01 << ones) - 1;
		}

	return answer;
}

 

실행 결과