(Java) 프로그래머스 - 2개 이하로 다른 비트

생각보다 시간이 꽤 걸렸던 문제였다.

처음에는 n+1 수부터  2진법으로 변환해서 비트가 2개 이하로 같다면 answer 배열에 넣어주는 것으로 풀었었다.

테스트 케이스가 통과되는 것을 보면서 쉬운 문제였구나 싶었는데 어림도 없지.. 10번 11번 케이스에서 시간 초과가 났다.

어떻게 접근해야 할지 환참을 고민했는데 질문하기 탭에서  numbers 배열의 값을 짝수와 홀수로 생각하면 된다는 힌트를 얻어서 풀이에 성공했다.

 

로직은 numbers 배열의 값을 짝수와 홀수로 나누는 것에서부터 시작한다.

짝수라면 2진법으로 변환했을때 가장 마지막 자리가 0으로 끝나므로 가장 마지막 자리를 1로 바꿔주면 10진법에서 1이 커진 숫자이기 때문이다.

 

홀수라면 한번 더 생각을 해야 한다.

2진법으로 변환했을 때 숫자가 1로만 이루어져 있는지, 0이 포함되어 있는지 나누어 생각해야 한다.

예를 들어 7은 2진법으로 변환했을 때 111로 1로만 이루어져 있다.

때문에 1110, 1101, 1011중 가장 작은 수를 선택해야 하는데 이 중 가장 작은 수는 1011이다.

이처럼 1로만 이루어진 수는 항상 1번 인덱스에 0을 추가하면 된다.

0이 포함되어 있는 수는 가장 마지막에 나오는 0을 찾아서 1로 바꿔주고 다음 자리를 0으로 바꿔주면 된다.

 

다른 분들 코드를 보니 비트 연산을 이용해서 풀이한 것도 있는데 나중에 한번 도전해봐야겠다.

 

---

최종 코드

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

        for (int i = 0; i < numbers.length; i++) {

            // 짝수라면
            if(numbers[i] % 2 == 0) {
                answer[i] = numbers[i] + 1;
                continue;
            }

            String n = Long.toString(numbers[i], 2);

            // 홀수이면서 1로만 이루어져 있다면
            if(!n.contains("0")) {
                // String 2번째 자리에 0 삽입
                String temp = n.substring(0, 1) + "0" + n.substring(1);
                // 10진수로 변환 후 answer 배열에 삽입
                answer[i] = Long.parseLong(temp, 2);
                // 홀수이면서 1과 0이 포함되어 있다면
            } else {
                // 마지막으로 0이 나오는 인덱스 찾기
                int idx = n.lastIndexOf("0");
                // 문자열 다시 만들기
                n = n.substring(0, idx) + "10" + n.substring(idx + 2);
                answer[i] = Long.parseLong(n, 2);
            }
        }
        return answer;
    }
}

 

실패 코드 (시간 초과 : 테스트 케이스 10, 11)

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

        for (int i = 0; i < numbers.length; i++) {
            long n = numbers[i] + 1;

            while (true) {
                if(Long.bitCount(numbers[i]^n) <= 2) {
                    answer[i] = n;
                    break;
                }
                n++;
            }
        }
        return answer;
    }
}