[프로그래머스,자바] Level2: 2개 이하로 다른 비트

 

문제의 이해

 

이 문제는  어느한 숫자 x를  2진법으로 치환한뒤,  그 2진법의 비트 1~2개가 다르며 보다 큰 수를 찾는 문제입니다.

 

 

비트가 1~2개 다르며 큰 수를 찾는방법을 찾는건 처음 생각하기에 매우 까다롭습니다.

 

따라서 차근차근 하나씩 경우의수를 찾아가며 규칙을 찾는게 중요합니다.

 

1.뒷자리가 00일경우 :  뒷자리가 00일경우,  바로 다음숫자가 조건에맞는 숫자입니다. 

EX) 100 ->101  비트가 1개다르며 큰 수

 

2.뒷자리가 01일경우 :  뒷자리가 01일경우, 바로 다음숫자가 조건에 맞는 숫자입니다.

EX) 101->110 비트가 2개 다르며 큰 수

 

3.뒷자리가 10일경우 : 뒷자리가 10일경우 , 바로 다음숫자가 조건에 맞는 숫자입니다.

EX) 110->111 비트가 1개 다르며 큰 수

 

4.뒷자리가 11일경우 : 뒷자리가 11일경우, 조금 다릅니다. 앞에있는 3가지경우는 바로 다음숫자가 조건에맞지만

11인경우는 다음숫자가 될수가없습니다.

EX) 11->101  ,   111->1011   , 1011->1101

EX2) 11->100(X) 3개가 다름   111->1000(X) 4개가다름

 

위 3개의 숫자가 해당하는 공통점을 찾아보면,

 

011의 01 부분을 10으로치환 : 101

0111의 01 부분을 10으로 치환 : 1011

1011의 01 부분을 10으로 치환: 1101 라는 공통점이 존재합니다.

 

이 모든과정을 로직에 담으면 문제는 해결됩니다.

 

 

1. 우선 뒷자리가 11이 아닌경우는 바로 다음숫자가 조건에 맞는숫자입니다.

 

이는 즉, 숫자를 4로 나눳을때 나머지가 3인 (뒷자리가 11) 경우를 제외한 모든숫자는 바로 다음숫자가 답입니다.

 

2. 뒷자리가 11인 경우는 특수 로직을 적용해야함.

 

그 특수 로직은  2진법으로 치환한 숫자에 (111)  0이없으면 임시적으로 0을붙이고, (0111) 

01 부분을 10으로 치환하는 과정입니다. (1011)

 

문제풀이

import java.util.*;
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for(int i=0;i<numbers.length;i++){
             if(numbers[i]%4==3){
               answer[i]=change(numbers[i]);
              }
             else{
               answer[i]=numbers[i]+1;
             }
        }
       
        return answer;
    }
    
    public long change(long numbers){
       
        long total=0;
        String temp="";
        boolean flag=false;
        
        while(numbers!=0){
           if(numbers%2==0){
               temp+='0';
               flag=true;
           }
           else{
               temp+='1';
           }
            numbers/=2;
        }
        if(flag==false){
            temp+='0';
        }
        temp=temp.replaceFirst("10","01");
        
 
        for(int i=0;i<temp.length();i++){
            if(temp.charAt(i)=='1'){
                total+=(long)Math.pow(2,i);
            }
        }
        
        return total;
    }
}