[알고리즘]프로그래머스 77885번 - 2개 이하로 다른 비트

프로그래머스 77885번 - 2개 이하로 다른 비트

프로그래머스 77885번 - https://programmers.co.kr/learn/courses/30/lessons/77885

 

요구사항

1. 정수들이 담긴 배열 numbers의 양수 x에 대하여 f(x)의 값을 배열에 차례대로 담아 반환하라.

 

f(x) = x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

 

요구사항 분석 및  풀이과정

1. 양수 x가 짝수인 경우 최하위 비트는 항상 0입니다. 그러므로 양수 x+1은 최하위 비트만 0에서 1로 바뀌게 됩니다. 따라 양수 x와 비트가 1개(최하위 비트)가 다르게 되고, f(x) = x + 1 이 성립합니다. 여기서 끝을 낼 수 있는 이유는, 양수 x+1은 x보다 큰 양수 중 제일 작은 수이기때문입니다.

 

 

f(x) = x + 1 ( x가 짝수 )

 

2. 양수 x가 홀수인 경우, 비트 1개 다르게 하는 직관적인 방법은 최하위 비트부터 최상위 비트까지 순회하여 처음으로 등장하는 1인 비트를 반전하는 것입니다. 그렇게 할 경우 결과는 x 보다 작아지게 됩니다.

 

3. 그렇다면 x보다 작아지지 않으면서 비트 1개가 다르게 하는 방법은 2번과 반대로 하면 됩니다. 처음으로 등장하는 0인 비트를 반전하는 것입니다.

 

4. 하지만 이 수가 f(x)를 만족할 수 있을까요? 확신할 수 없습니다. 당장 f(7)만 봐도 3번의 방법대로 f(7)을 구하게 되면 다음과 같습니다.

 

 

f(7) = 15가 나오게 되며, 이는 실제 올바른 값 f(7) = 11이 아닙니다. 왜 그럴까요? f(x)는 비트가 1개 다른 수들 중에서 제일 작은 수가 아니라 비트가 1~2개 다른 수들 중에서 제일 작은 수이기 때문입니다.

 

비트가 1개 다른 수 중에서는 제일 작은 수라고 확신할 순 있지만, 비트가 2개 다른 수 중에서는 제일 작은 수라고 확신할 순 없습니다.

 

그렇다면 어떻게 해야 할까요? 정답은 간단합니다. 반전시켜준 비트의 우측 비트(항상 '1'입니다. 왜 그런지 모르겠으면 3번을 다시 읽어보세요)를 반전하여주면 됩니다. 그러면 비트가 2개가 다르면서 제일 작은 수가 될 수 있습니다.

 

왜 그럴까요? 반전시킨 비트의 좌측 비트들을 조작하게 될 경우 어떤 비트를 조작하든 수는 커지게 됩니다. 그렇기 때문에 우리는 하나의 비트를 더 조작하여 2개의 비트를 다르게 만들고 싶다면 그 선택지는 반전시킨 비트의 우측 비트들 밖에 없는 것이 자명합니다.

 

"우측 비트들밖에 선택지가 없다는 건 알겠는데, 왜 그러면 바로 옆 비트인가요?"라고 물을 수 있습니다.

 

또한 반전시킨 비트의 우측 비트들은 모두 1이며, 그 비트들 중 한 비트를 반전시킨다는 것은 해당 비트에 해당하는 수를 뺀다는 것을 의미합니다. 우리는 비트가 1~2개 다른 수 중 제일 작은 수를 원합니다. 

 

그렇기 때문에 반전시킨 비트의 우측 비트들 중 가장 큰 수에 해당 비트, 즉 반전시킨 비트의 바로 우측의 비트를 반전시키면 양수 x보다 큰 수  중 비트 1~2개를 다른 수들 중에서 제일 작은 수임이 자명합니다.

 

비트 마스킹에 대하서 알아보자.

우리는 처음으로 등장하는 0'비트를 알기 위하여, 특정 k(>=0) 번째 비트의 값이 0인지 1인지를 알아야 합니다. 어떻게 알 수 있을까요?

 

이때 k는 최하위 비트로부터 오프셋을 의미합니다.

 

흔히 이러한 문제를 해결하는 방법들을 비트 마스킹이라고합니다.

 

k번째 비트의 값을 어떻게 알 수 있을까!?

정수 n의 k번째 비트가 1인지, 0인지를 확인하는 방법은 & 연산의 특징을 이용하면 간단합니다.

 

& 연산은 피연산자가 1bit일 경우 두 비트가 모두 1인 경우 1, 그렇지 않은 경우는 0을 반환합니다. 1bit가 아닌 경우 각 bit에 대하여 동일한 작업을 수행합니다.

 

이 특징을 이용하여 k번째 비트를 제외한 모든 비트가 0, k번째 비트만 1인 정수를 정수 n과 & 연산을 할 경우, 정수 n의 k번째 비트를 제외한 모든 비트는 0으로 바뀐 수, 정수 n의 k번째 비트만 남은 수가 반환되는 거죠.

 

그렇다면 k번째 비트만 1인 정수는 어떻게 구할까요? 이는 쉬프트 연산자(<<)를 이용하면 간단합니다. 정수 1을  k번 좌측으로 비트를 밀게 되면 k번째 비트만 1인 정수가 됩니다.

 

 

0번째 비트만 1인 정수는 정수 1을 0번 좌측으로 비트를 밀면 0번째 비트만 1인 정수입니다.

1번째 비트만 1인 정수는 정수 1을 1번 좌측으로 비트를 밀면 1번째 비트만 1인 정수입니다.

2번째 비트만 1인 정수는 정수 1을 2번 좌측으로 비트를 밀면 2번째 비트만 1인 정수입니다.

 

k번째 비트만 1인 정수는 정수 1을 k번 좌측으로 비트를 밀면 k번째 비트만 1인 정수입니다.

 

 

다음은 정수 7의 2(k=2) 번째 비트에 해당하는 수를 구하기 위하여 정수 7과 정수 1을 2번 좌측으로 비트를 민 정수 4(1 << 2)와 & 연산을 한 모습입니다.

 

 

그 결과 정수 7의 2번째 비트의 값만 설정된 비트열 0b0100을 얻은 모습입니다. 만약 2번째 비트가 0이었다면 결과는 0일 것이고, 1이었다면 2^k가 결과일 것입니다.

 

정수 n의 k번째 비트가 0인 경우 - n & (1 << k) = 0

정수 n의 k번째 비트가 1인 경우 - n & (1 << k) = 2^k

 

 

따라서 우리는 n & (1 << k)의 결과가 0이냐 아니냐로 k번째 비트가 1인지 0인지를 구별할 수 있게 되었습니다. 

 

k번째 비트만 어떻게 하면 변경할 수 있을까!?

k번째 비트를 1로 바꾸는 것과, 0으로 바꾸는 것으로 방법을 나눠볼 수 있습니다.

 

결과부터 말하자면 1로 바꾸는 것은 | 연산자를 이용하여, 0으로 바꾸는 것은 & 연산을 이용하여 할 수 있습니다. 우리는 앞서 k번째 비트의 값을 확인하는 방법을 알아보았습니다. 그 원리를 이용하면 k번째 비트의 값을 원하는 값(1 또는 0)으로 바꾸는 것 또한 쉽게 가능합니다.

 

그 방법은 이 글을 읽는 여러분께 숙제로 남기겠습니다.

방법이 궁금하다면 소스코드에서 turnOn, turnOff 메서드를 확인하여 주세요.

 

소스코드 작성

class Solution {

	private boolean isTurnOn(long n, int pos) {
		return (n & (1L << pos)) != 0;
	}

	private long turnOn(long n, int pos) {
		return n | (1L << pos);
	}

	private long turnOff(long n, int pos) {
		return n & (~(1L << pos));
	}

	private long solve(long n) {
		if ((n & 1L) == 0) {
			return n + 1;
		}

		for (int pos = 0; pos < 50; pos++) {
			if (!isTurnOn(n, pos)) {
				return turnOff(turnOn(n, pos), pos - 1);
			}
		}

		return n;
	}

	public long[] solution(long[] numbers) {
		long[] result = new long[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			result[i] = solve(numbers[i]);
		}

		return result;
	}
}

 

결과

 

소스코드 깃허브 주소

링크