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

프로그래머스에 새롭게 보이는 문제가 있어 도전하였습니다.

처음 문제에 접근할 때는 다음 로직으로 프로그래밍 하였습니다.

1) 주어진 숫자 N에 대해 이진수로 변경한다.

2) 주어진 숫자 N에 대해 순차적으로 1씩 증감시키면서 (1)에서 변경한 이진수와 비교하여 자릿수 숫자의 차이가 2개 이하인 경우에 대해 answer를 return 한다.

위 로직을 수행할 경우 시간 초과가 발생하게 됩니다.

생각해보면 numbers의 모든 수가 10의 15승이기 때문에 최악의 경우 10의 15승이 될 수 있기 때문에 사실상 정답이 될 수 없는 로직입니다. 

그 다음 문제를 접근할 때는 규칙에 주목하였습니다. 

문제에서 제공되는 예시를 가지고 생각해봤습니다.

7=0111 에 대해 다른 비트의 개수는 11=1011 이 됩니다. 

비트를 잘 살펴보면 
0111
1011 

0111의 경우 최소 1000은 되어야 기존 0111(=7) 보다 커지게 됩니다. 1000이 8이므로
따라서 현재 주어진 비트의 자릿수를 순회하면서 최초 0인 구간을 1로 변경해 줍니다.

그러면 1111이 되는데, 기존 0111과 비트 자릿수 차이는 1입니다. 그러나, 1111(=15)이 자릿수가 다른 비트의 개수가 최소가 되지 않기 때문에 값은 최소 + 비트의 개수가 2개 이하인 경우를 찾아야 합니다. 

가장 간단한 방법은 무엇일까요?

1111에서 바로 0👉1 로 바꾼 인덱스 바로 뒤의 값이 1인 경우 0으로 바꾸면 됩니다. 그러면 0인 경우는 1로 바꾸는지? 이런 경우는 나올 수 없습니다. 이미 0👉1 로 바꾼 경우 그 이전 비트는 무조건 1입니다. (최초의 0인 경우만 1로 변경하기 때문에)

하나 더 예를 들어보겠습니다.

2(=10) 도 0인 지점을 1로 변경합니다. 11, 1 다음 비트는 없으므로 그대로 둡니다. 3이 최소가 됩니다.

위 내용을 도식화 해보면 다음과 같습니다. 

 

google docs로 열심히 적어보았다..

이 내용을 바탕으로 JAVA로 코드를 구성해보았습니다.

Java에서 제공하는 함수로 toBinaryString를 이용해 기존 N의 값을 이진수를 쉽게 변경할 수 있습니다.

그 다음 로직은 위에 설명한 것을 그대로 구현하였습니다.

memoryIdx는 11 이런 값에 대해 구별하기 위함입니다. 11이 저장되어 있어서 011로 인식하기 위해, 그래서 111로 만들어주는것입니다.

위 내용을 그대로 코드로 구현한 것이라 다양한 방법으로 프로그래밍 할 수 있습니다. 

import java.util.*;
import java.io.*;
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for(int i=0; i<numbers.length; i++){
            String binary = Long.toBinaryString(numbers[i]);
            // System.out.println(binary);
            char[] strToChar = binary.toCharArray();
           
            int memoryIdx = -1;
            //System.out.println(Arrays.toString(strToChar));
            for(int j=strToChar.length-1; j>=0; j--){
                if(strToChar[j]=='0'){
                    memoryIdx = j;
                     // System.out.println(memoryIdx);
                    strToChar[j]='1';
                  
                    break;
                }
            }
            
             //System.out.println(Arrays.toString(strToChar));
           
            if(memoryIdx == -1){
                binary = "1"+binary;    
                strToChar = binary.toCharArray();
                if(strToChar[1]=='1')
                    strToChar[1]='0';
            }else{       
                //System.out.println("else");
                if(memoryIdx+1<strToChar.length && strToChar[memoryIdx+1]=='1'){
                    strToChar[memoryIdx+1]='0';
                }
                
            }
            //System.out.println(Arrays.toString(strToChar));
            // System.out.println(Arrays.toString(strToChar));
           
            long sum = 0;
            int cnt = 0;
            for(int j=1; j<=strToChar.length; j++){
               sum+=(Math.pow(2,cnt++)*Long.parseLong(""+strToChar[strToChar.length-j]));
                // System.out.println("pow : "+Math.pow(2,j-1));
            }
            answer[i] = sum;
        }
        return answer;
    }
}