[programmers] 29. 2개 이하로 다른 비트

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

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

 

1. Problem

문제 설명

양의 정수 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의 모든 수 ≤ 1015

---

입출력 예

numbersresult

[2,7]

[3,11]

 

2. Code

package programmers;

public class skillTestLevel2 {

	// 이진수의 숫자가 2이하로 차이나고 입력값보다 큰 수 찾기
	public static void main(String[] args) {
		long[] numbers = {2,7};
		solution(numbers);

	}
	public static long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for(int i = 0; i < numbers.length; i++) {
        	if(numbers[i] == 1) {
        		answer[i] = 2;
        	} else {
        		String s = Long.toBinaryString(numbers[i]);
            	for(int j = s.length()-1; j >= 0; j--) {
            		if(s.charAt(j) == '0' && j == s.length()-1) {
            			answer[i] = Long.parseLong(s.substring(0,j) + "1", 2);
            			break;
            		} else if(s.charAt(j) == '0' && j == s.length()-2) {
            			answer[i] = Long.parseLong(s.substring(0,j) + "1" + "0", 2);
            			break;
            		} else if(s.charAt(j) == '0' && j < s.length()-2) {
            			answer[i] = Long.parseLong(s.substring(0,j) + "1" + "0" + s.substring(j+2), 2);
            			break;
            		} else if(s.charAt(j) == '1' && j == 0) {
            			answer[i] = Long.parseLong("1" + "0" + s.substring(1), 2);
            			break;
            		}
            	}
        	}
        }
        return answer;
    }
}

 

3. Report

주어진 수의 이진수에 0이 있냐 없냐로 나눠서 생각할 수 있다.

 

0이 있을 경우 맨 마지막 비트가 0이면 맨 마지막 비트를 1로 바꿔주면 된다. 

ex) 1110 -> 1111

 

중간 비트가 0일 경우에는 최대 2비트까지 다를 수 있으므로 뒤에 1비트를 0비트로 바꿔준다 (가장 작은 값이여야함)

ex) 1101 -> 1110 , 1011 -> 1101

 

마지막으로 모든 수가 1일 경우엔 가장 앞에 1을 붙이고 그다음 비트를 0으로 바꿔준다 

ex) 111 -> 1011