[Java] 프로그래머스(level-2) - 2개 이하로 다른 비트
문제 풀이
이번 문제는 문제의 요구사항대로 비트를 활용해 구현하면 되는 문제이다.
아아디어 도출
비트연산자를 활용하면 풀 수 있을 것으로 보이나 필자는 비트연산에 대해서 부족한 점이 많아 규칙을 찾아서 풀었다.
정수를 비트(2진수)로 변환한 후, 이 수보다 큰 수이면서 비트일 때의 차이가 1~2개이여야 한다. 여기서 어떤 규칙을 찾아낼 수 있을까?
먼저 십진수 1부터 6까지를 비트로 표현해보자.
| 십진수/비트 | 16 | 8 | 4 | 2 | 1 |
|---|---|---|---|---|---|
| 1 | 1 | ||||
| 2 | 1 | 0 | |||
| 3 | 1 | 1 | |||
| 4 | 1 | 0 | 0 | ||
| 5 | 1 | 0 | 1 | ||
| 6 | 1 | 1 | 0 |
잘보면 짝수일 때는 모두 0으로 끝나는 것을 알 수 있다. 그렇다면 여기서 짝수의 규칙을 찾아낼 수 있다!
짝수일 때의 규칙 비트의 끝자리가 0인, 즉 짝수인 십진수의 경우 +1인 값이 조건에 충족된다.
Ex.2(10) -> 3(11),4(100) -> 5(101),6(110) -> 7(111)
짝수의 규칙은 쉽지만, 홀수의 규칙을 찾기가 어려웠다. 홀수의 경우는 끝자리가 1인데, 비트값을 기준으로 0이 섞인 홀수와 0이 없는 홀수로 나뉘게 된다.
홀수일 때의 규칙
- 0이 존재할 경우, 하위 비트에서부터 “01”을 찾아 “10”으로 바꾼다.
Ex.5(101) -> "1" + "10" = "110",9(1001) -> "10" + "10" = "1010"- 0이 없을 경우, 큰 수이면서 가까운 수이려면 상위비트에 0을 삽입한다.
Ex.7(111) -> "10" + "11" = "1011",11111 -> "10" + "1111" => "101111"
위와 같이 주어진 수가 짝수일 경우와 홀수일 경우를 나누어 규칙을 반영하여 조건에 맞는 십진수를 배열에 담아 반환하면 된다.
다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public long[] solution(long[] numbers) {
long[] answer = new long[numbers.length];
for(int i=0; i<numbers.length; i++) {
/*
* numbers의 원소가 짝수일 경우
* 해당 수의 바로 다음 비트는 다른 점이 1개이면서 큰 수라는 조건을 충족한다.
* f(n) = n + 1
*/
if(numbers[i] % 2 == 0) {
answer[i] = numbers[i] + 1;
continue;
}
/*
* numbers의 원소가 홀수일 경우
* 해당 수의 최하위 비트(마지막)부터 "01"을 찾아 "01"이 있다면, "10"으로 바꿔준다.
* "01"이 없다면 최상위 비트(처음)를 제거하고 "10"을 추가한다.
* 변환한 비트인 2진수를 Long형 타입으로 변환하여 배열에 삽입한다.
*/
String binary = Long.toBinaryString(numbers[i]);
// 해당 2진수에서 "01"의 인덱스를 마지막 비트에서부터 찾아 "10"으로 변환한다.
int zeroIdx = binary.lastIndexOf("01");
if(zeroIdx != -1) {
binary = binary.substring(0, zeroIdx) + "10" + binary.substring(zeroIdx+2, binary.length());
answer[i] = Long.parseLong(binary, 2);
continue;
}
// "01"이 없다면 상위 비트 하나를 제거하고 "10"을 삽입한다.
binary = "10" + binary.substring(1, binary.length());
answer[i] = Long.parseLong(binary, 2);
}
return answer;
}
public static void main(String[] args) {
Solution sol = new Solution();
long[] numbers = new long[]{2, 7};
// long[] numbers = new long[]{5, 7, 11};
// long[] numbers = new long[]{1001,337}; // 1002, 338
sol.solution(numbers);
}
}
회고
-
출처
-
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.