[프로그래머스] 2개 이하로 다른 비트 (월간 코드 챌린지 시즌2)

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

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

2021-07-29

---

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 || numbers[i] % 4 == 1) answer[i] = numbers[i] + 1;
            else {
                String val = Long.toBinaryString(numbers[i]);
                if ((numbers[i] + 1) % 4 == 0) val = "0" + val;
                int index = val.lastIndexOf("01");
                val = val.substring(0, index) + "10" + val.substring(index + 2, val.length());
                answer[i] = Long.parseLong(val, 2);
            }
        }
        return answer;
    }
}

#문제풀이

 

규칙을 찾는데 되게 오래 걸렸다. 실제 시험이었으면 좀 멘붕 왔을 수도,,? 

 

1. 짝수는 +1을 해주면 된다. 

 

2. 홀수의 경우 복잡해진다. 

1) 아래와 같이 +1 만 되는 경우는 4로 나눴을 때 나머지가 1인 경우여서 짝수와 함께 묶어줬다. 

3 -> 5

5 -> 6

7 -> 11

9 -> 10

11 -> 13

13 -> 14

15 -> 23

17 -> 18

19 -> 21

 

2) 그 외 나머지 홀수의 경우는 가장 나중에 나온 01이 10으로 바뀐다는 규칙을 찾아서, 바꿔줬다. 그리고 값+1 했을 때 4로 나눠떨어지는 경우에는, 앞에 0도 붙여주었다.

3 -> 5

011 -> 101

 

7 -> 11

0111 -> 1011

 

11 -> 13

1011 -> 1101

 

15 -> 23

01111 -> 10111

 

19 -> 21

10011 -> 10101

 

 

나는 이렇게 힘들게? 억지로? 풀었고, 다른 사람들은 어떻게 풀었나 찾아봤다.

프로그래머스에서 되게 신기한 풀이를 봤다. 

 

현재 array를 복사한다음에 복사된 array를 ++ 해주고 기존 값과 +1 된 값을 xor연산을 해주고 >>> 2 연산을 해준 후 다시 복사된 array에 더해준다. 

 

연산을 풀어보니 이해는 되는데 어떻게 생각했는지 모르겠다,,