[JAVA] 프로그래머스 - 2개 이하로 다른 비트

문제내용

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

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

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수비트다른 비트의 개수

2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수비트다른 비트의 개수

7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10^15

---

문제 풀이

처음엔 제한사항을 고려하지 않고, 탐색하는 수를 2진수로 바꾸고 숫자를 하나씩 올려가면서 비교를 해나갔다. 그 결과 1~8번까지 테케는 맞는데 9~10번이 테케에서 시간초과에 걸렸다. 이후에 제한사항을 보니 숫자는 최대 십만개였고, 반복문을 돌리면 최악의 경우 십만*10^15가 되기 때문에 당연히 걸리는게 맞았다.

 

그래서 다른 사람들의 풀이를 봤는데, 공통적인건 내가 처음에 했던것처럼 하나씩 비교해나가는 반복문이 아니라

numbers[i]의 숫자가 짝수일때와 홀수일때로 나눠서 최솟값을 구했다는 점이다.

 

짝수일때

짝수를 2진수로 바꾸면 무조건 1의 자리는 0이된다.

따라서 1의 자리에 +1 한 값은 홀수가 됨과 동시에 기존의 수와 비트가 1개 차이나며, 가장 작은수가 된다.

 

홀수일때

홀수는 마지막으로 0이 나오는 위치를 찾는게 우선이다.

이유는 마지막으로 0이 나오는 위치에서 0을 1로 바꾸기 위함이다.(여기서 기존의 숫자보다 커야한다는 조건 만족)

또 다른 이유는 마지막으로 0이 나오는 위치에서 다음 숫자는 무조건 1이라는 것을 알아야한다(2진수니까 당연함). 그리고 그 1을 0으로 바꾼다.(여기서 기본의 숫자보다 크면서 조건에 맞는 비트 차이가 나고, 가장 작은 숫자가 됨)

만약 0을 못찾았다면 가장 앞자리의 1을 "10" 으로 바꿔주면 해결된다. (위의 원리와 같음.)

 

ex> 11 (3) -> 101 (5)

ex> 111 (7) -> 1011 (11)

 

 

---

코드

public class Solution {
	public static long[] solution(long[] numbers) {
		long[] answer = new long[numbers.length];
		
		for(int i=0; i<numbers.length; i++) {
			String binary = Long.toString(numbers[i],2);//2진수 변환
			if(numbers[i]%2==0) {
				//짝수라면 2진수일때 일의 자리는 무조건 0임.
				//그래서 일의 자리에 +1하면 홀수가 되고 가장 작은수이면서 비트차이가 1차이나는 수가됨.
				answer[i] = numbers[i]+1;
			}else {
				int zeroIdx = binary.lastIndexOf('0');//마지막 0의 위치를 찾음.
				if(zeroIdx!=-1) {//0이 있다면
					//마지막 0의 자리와 그다음 자리를 바꿔준다 -> 한마디로 "01" -> "10" 으로 바꿔줌(마지막 0의 자리다음은 무조건 1임, 이유는 2진수잖아)
					binary = binary.substring(0,zeroIdx) + "10" + binary.substring(zeroIdx+2,binary.length());
					answer[i] = Long.parseLong(binary,2);
				}else {//0이 없다면
					//0이 없으면 가장 앞에 자리에 있는 1을 "10"으로 바꿔줌(이 경우는 f(3) = 5 or f(7) = 11 을 생각해보면됨)
					binary = "10" + binary.substring(1,binary.length());
					answer[i] = Long.parseLong(binary,2);
				}
			}
		}
		
		return answer;
	}
}

---

마치며

단순한 반복문으로 비교탐색을 해서는 풀수 없는 문제이고, 이렇게 조금은 수학적으로 접근해야 하는 문제에 대한 연습이 필요하다.