프로그래머스 lv2 2개 이하로 다른 비트

문제 링크

2개 이하로 다른 비트

풀이

처음에는, '비트'라는 문자가 제목에 있었고, 문제 내용도 간단하게 XOR 비트 연산을 이용해서 하면 될 것 같았다.

그래서 그 대로 문제를 아래와 같이 풀었다.

public class 두개이하로다른비트 {
	public long[] solution(long[] numbers) {
		long[] answer = new long[numbers.length];

		for (int i = 0; i < numbers.length; i++) {
			long number = numbers[i];
			long compareNumber = numbers[i] + 1;
			while (true) {
				long bitGapCnt = countBitGap(number, compareNumber);
				if (bitGapCnt <= 2) {
					answer[i] = compareNumber;
					break;
				}
				compareNumber += 1;
			}
			answer[i] = checkMinBitNum(numbers[i]);
		}
	}
    
	// xor 연산을 이용한 방법
	public long countBitGap(long a, long b) {
		String xorResult = Long.toBinaryString(a ^ b);
		return Arrays.stream(xorResult.split("")).filter(i -> i.equals("1")).count();
	}
 }

XOR 연산을 이용해서 비트가 다른 경우 1을 찍어주게 한 다음, 1의 개수를 세었다.

그러나 이 경우 테스트 케이스 마지막 2개에서 넘어가질 못했다.

다른 방법이 없을까.. 하다가 규칙성을 하나 발견했다.

짝수인 경우 2진수로 변경한 수에 +1 을 해주면 되고,

홀수인 경우, 오른쪽에서부터 0을 탐색하다가, 0이 존재하면 0을 1로 바꾼 뒤, 그 다음에 오른쪽의 수를 0으로 바꾸면 된다.

(111과 같이 모두 1인 경우, 맨 앞에 0을 더해주고 그 다음에 규칙을 따른다.)

위의 규칙을 기반으로 짠 코드는 다음과 같다.

import java.util.Arrays;
import java.util.stream.Collectors;

class Solution {
	public long[] solution(long[] numbers) {
		long[] answer = new long[numbers.length];

		for (int i = 0; i < numbers.length; i++) {
			answer[i] = checkMinBitNum(numbers[i]);
		}

		return answer;
	}

	public long checkMinBitNum(long a) {
		boolean isEven = a % 2 == 0;
		String binaryString = Long.toBinaryString(a);

		char[] charArray = binaryString.toCharArray();
		if (isEven) {
			charArray[charArray.length - 1] = '1';
			return Long.parseLong(String.valueOf(charArray), 2);
		}

		// 홀수인 경우 모든 수가 1인 경우가 있다.
		// 이런 경우는 맨 앞에 0을 더해서 확인한다.
		if(!binaryString.chars().mapToObj(c -> (char)c).collect(Collectors.toList()).contains('0')){
			binaryString = "0" + binaryString;
		}

		charArray = binaryString.toCharArray();
		for (int i = charArray.length - 1; i >= 0; i--) {
			char c = charArray[i];
			if (c == '0') {
				charArray[i] = '1';
				if(i != charArray.length -1){
					charArray[i + 1] = '0';
				}
				break;
			}
		}

		return Long.parseLong(String.valueOf(charArray), 2);
	}
}