[프로그래머스] level2. 2개 이하로 다른 비트 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. 2개 이하로 다른 비트 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/77885

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

---

# 접근 방법 및 풀이 

 

• 이거 규칙찾느라 시간이 너무 오래 걸린 문제다. 첫번째 풀이는 시간초과 났고, 규칙 찾아서 두번째 풀이로 통과했다.
• 첫번째 풀이는 일단 풀어야겠다 싶어서 무식하게 짠 코드다.
• 예를들어 7이라면 +1씩 더하면서, 그숫자를 2진수로 바꾸고 XOR 비트 연산해서 1의 갯수가 2보다 작으면 답으로했다.
• 역시나 테케 마지막 두개가 시간초과 나서 틀렸다 ^^...
• 그리고 찾은 방법은 숫자가 짝수일 때 홀수일 때를 나눠서 풀었다.
• 먼저, 십진수 1~6을 2진법으로 표현하면 다음과 같다. 여기서 짝수라면 끝이 0으로 끝나는 것을 알 수 있다.

• 16	8	4	2	1
  				1
  			1	0
  			1	1
  		1	0	0
  		1	0	1
  		1	1	0

• 끝자리가 0이고, 비트를 하나 바꾸면서 현재값보다 큰 수는 +1해주면 된다. 따라서 10 -> 11이 될 것이고, 1010 -> 1011이 될것이다.
• 그래서 numbers[i] 값이 짝수면 answer[i] = numbers[i]+1 해주면 된다.
• 문제는 홀수다. 홀수일 땐 맨 끝이 1로 끝난다. 이때 경우의 수는 2가지로 나뉘어진다.
• 11111 < 1로만 이루어진 홀수와, 101011 < 1과 0이 섞인 홀수로 나누어 풀어준다.
• 먼저 1로만 이루어진 홀수보다 큰 수가 나오려면 자릿수가 하나 늘어난다.
• 예를 들어 1111이라면, _ _ _ _ _ 5자리 이진수가 나온다. 여기서 생각해볼 점은 이미 자릿수가 하나 커지므로 비트 하나는 다르게 나온다. -> 1111, 1_ _ _ _ 
• 1_ _ _ _ 그럼 여기서 비트 하나를 더 바꿀 수 있는데, 1 1 1 1 1  중에 한 자리 수를 0으로 바꾸면 된다.
• 11111에서 숫자가 가장 작아지려면 앞쪽에 0을 넣어야한다. 따라서 10111이 된다.
• 이걸 쉽게 생각하면, 1로 이루어진 홀수가 나올 경우, "10"을 앞에 붙이고 기존 홀수에서 자릿수를 하나 빼고 더해주면된다.
• ex) 111 -> "10" +"11" => "1011" 이 나온다. 
• ex) 11111 -> "10" + "1111" => "101111"
• 그럼 이제 0이 섞여있는 홀수이다. 

• 1	0	0	1
  1	0	1	0

• 1001일 경우, 끝에서 부터 처음 0이 나오는 곳을 1로 바꾸고 끝자리 1을 0으로 바꾸면 된다.
• 자세한건 코드참조!
• 다른 풀이보니까 비트연산으로 풀었던데,, 비트 연산은 생각해보기 어렵다. 

# 주의할 점 

 

• Integer가 아닌 Long형!

 

JAVA 코드

시간초과 코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for(int i = 0; i < numbers.length; i++){
            long num = numbers[i]+1;
            while(true){
                if(Long.bitCount(numbers[i]^num) <= 2){
                    answer[i] = num;
                    break;
                }
                num++;
            }
        }
        return answer;
    }
}

통과 코드

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;
            else{
                String s = Long.toString(numbers[i],2);
                int zeroIdx = s.lastIndexOf("0");
                if( zeroIdx != -1){
                  s = s.substring(0, zeroIdx) + "10" + s.substring(zeroIdx+2, s.length());
                  answer[i] = Long.parseLong(s,2);
                }else{
                   s = "10" + s.substring(1,s.length());
                   answer[i] = Long.parseLong(s,2);
                }
            }
    
        }
        return answer;
    }
}

 

 

REVIEW