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

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

프로그래머스

코딩테스트 연습 > 월간 코드 챌린지 시즌2 > 2개 이하로 다른 비트

 

난이도: LEVEL2

알고리즘 유형: 구현

 

문제 풀이

처음에는 1씩 증가시켜서 비트 차이가 1~2 차이 나는 숫자를 구할려고 했었다. 

하지만 해당 풀이는 테스트케이스 10,11에서 시간 초과가 발생한다. 

아마 비트 차이가 1~2인 숫자가 기존 숫자보다 훨씬 커서 시간 초과가 발생하는듯하다. 

ex) 101111111111111111111111111111 -> 110111111111111111111111111111

import java.util.*;
class Solution {
    static long [] answer;
    static StringBuilder sb = new StringBuilder(); // 객체 재사용 
    public long[] solution(long[] numbers) {
        answer = new long [numbers.length];
        for(int i = 0; i < numbers.length; i++){
            find(numbers[i], i);
        }
        return answer;
    }
    public static void find(long num, int index){
        long start = num + 1;
        String str = toBinary(num);
        while(true){
            String test = toBinary(start);
            int cnt = 0;
            cnt += test.length() - str.length();
            int test_idx = cnt;
            for(int i = 0; i < str.length(); i++){
                if(cnt >= 3) break;
                if(str.charAt(i) != test.charAt(test_idx++)) cnt++;
            }
            if(cnt <= 2){
                answer[index] = start;
                break;
            }
            else start++;
        }
    }
    public static String toBinary(long num){
        sb.setLength(0);
        while(num >= 2){
            sb.append(num % 2);
            num /= 2;
        }
        sb.append(num);
        return sb.reverse().toString();
    }
}

 

어떻게 시간 복잡도를 줄일까?

잘 생각해보니 해당 숫자보다 크고 비트 수가 1 ~ 2만 차이나는 숫자중에서 가장 작은 숫자는 

아래 3가지 케이스로 쉽게 구할 수 있었다. 

3가지 case
0이 맨 뒤에 있는 경우 
10 -> 11 / 110 -> 111

0이 중간에 있는 경우 
101 -> 110 / 1001 -> 1010 / 10111 -> 11011 

0이 없는 경우 
111 -> 1011  / 1111 -> 10111

이 3가지 말고는 다른 예외 케이스는 존재하지 않는다. 

0이 가장 맨 뒤에 있으면 그냥 0을 1로 교체 

0이 중간에 있으면 가장 큰 index의 0을 기준으로 해당 숫자를 1로 바꾸고 오른쪽을 0으로 바꾼다.  

0이 없는 경우는 1을 추가하고 바로 오른쪽을 0으로 바꾼다. 

정답 코드 

import java.util.*;
class Solution {
    static long [] answer;
    static StringBuilder sb = new StringBuilder ();
    public long[] solution(long[] numbers) {
        answer = new long [numbers.length];
        for(int i = 0; i < numbers.length; i++){
            func(i, numbers[i]);
        }
        return answer;
    }
    public static void func(int index, long cur){
        String str = toBinary(cur);
        int lastIndex = -1;
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) == '0') lastIndex = i;
        }
        long result = 0;
        int size = str.length();
        // 0이 없는 경우 
        if(lastIndex == -1){
            result = toLong("10" + str.substring(1, size));
        }
        else{
            // 제일 끝에 있는 경우 
            if(lastIndex == str.length() - 1){
                result = toLong(str.substring(0, size -1) + "1");
            } 
            // 가운데에 0이 있는 경우 
            else{
                result = toLong(str.substring(0, lastIndex) + "10" + str.substring(lastIndex + 2));
            }
        }
        
        answer[index] = result;
    }
    // long -> (String)Binary
    public static String toBinary(long num){ 
        sb.setLength(0);
        while(num >= 2){
            sb.append(num % 2);
            num /= 2;
        }
        sb.append(num);
        return sb.reverse().toString();
    }
    // (String)Binary -> long 
    public static long toLong(String str){
        long sum = 0;
        int cnt = 0;
        for(int i = str.length() - 1; i >= 0; i--){
            if(str.charAt(i) == '1'){
                sum += (long) Math.pow(2, cnt);
            }
            cnt++;
        }
        return sum;
    }
}