🎯문제
양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.
x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
예를 들어,
f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.
| 수 | 비트 | 다른 비트의 개수 |
|---|---|---|
| 2 | 000...0010 | |
| 3 | 000...0011 | 1 |
f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.
| 수 | 비트 | 다른 비트의 개수 |
|---|---|---|
| 7 | 000...0111 | |
| 8 | 000...1000 | 4 |
| 9 | 000...1001 | 3 |
| 10 | 000...1010 | 3 |
| 11 | 000...1011 | 2 |
정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ numbers의 길이 ≤ 100,000
0 ≤ numbers의 모든 수 ≤ 1015
입출력 예
| numbers | result |
|---|---|
| [2,7] | [3,11] |
입출력 예 설명
입출력 예 #1
문제 예시와 같습니다.
✏️풀이
코드
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) {
// number[i] 값에서 1만 증가시켜주면 됨
answer[i] = numbers[i] + 1;
}
// 홀수일 경우
else {
// numbers[i]를 2진수 문자열로 저장
String x = Long.toString(numbers[i], 2);
// 0이 들어간 마지막 인덱스의 위치를 저장
int zeroIndex = x.lastIndexOf("0");
String y = "";
// 0이 존재한다면
if(zeroIndex != -1) {
// 인덱스 이전까지의 값 + "10" + (인덱스+2) 이후의 값
y = x.substring(0, zeroIndex) + "10" + x.substring(zeroIndex+2);
}
// 0이 존재하지 않는다면
else {
// "10" + 인덱스 1 이후의 값
y = "10" + x.substring(1);
}
answer[i] = Long.parseLong(y, 2);
}
}
return answer;
}
}설명
문자열의 함수들을 사용하여 문제를 풀었다.
값을 하나하나 비교해주는 방식도 생각을 해보았으나 문자열의 길이와 일일이 비교한다고 생각하니 시간초과의 걱정이 들었다. 따라서 규칙을 찾아서 문제를 해결해보고자 하였다.
가장 먼저 짝수와 홀수의 경우를 나누어서 생각해주었다.
짝수를 2진수로 나타낼 경우 무조건 맨 마지막 비트는 0으로 남게 된다. 마지막 비트는 1을 뜻하며 짝수일 때는 해당 비트가 채워질 수 없기 때문이다.
따라서 짝수일 때 자신보다 크면서 2개 이하의 비트가 다른 경우는 바로 다음 수가 된다.
예를 들어,
2의 경우 0010이고, 정답은 0011인 3이 된다.
4의 경우 0100이고, 정답은 0101인 5가 된다.
6의 경우 0110이고, 정답은 0111인 7이 된다.
이처럼 짝수는 자신보다 하나 큰 수가 정답이 되는 것이다.
홀수를 2진수로 나타냈을 경우는 다시 2가지의 경우로 또 나눠지게 된다.
첫번째는 0이 포함이 되었을 경우와 두번째는 0이 포함되지 않았을 경우이다.
먼저 0이 포함되었을 경우의 예를 들어보면,
11의 경우 1011이다. 이때 정답은 1101이 된다. 다른 숫자를 한번 더 살펴보자
13의 경우 1101이다. 이때 정답은 1110이 된다.
위에 2가지 경우처럼 0이 포함된 "01"이라는 값을 "10"으로 바꿔줘야한다는 것을 알 수 있다.
이때 0이 여러 개가 나올 수 있는데 우리는 가장 작은 숫자를 구해야하기 때문에 lastIndexOf("0")를 사용하여 0이 들어간 마지막 인덱스의 위치를 저장해준다.
그리고 substring을 통해 0의 이전까지 값을 가져오고, "10"을 저장한 뒤 저장된 값까지의 길이를 제외한 남은 길이를 가져온다.
1011로 예를 들자면, 1 + 10 + 1이 되는 것이다.
0이 포함되지 않았을 경우의 예는 입출력 예시에 나와있다.
7의 경우 0111이 되는데 정답은 1011인 11이 된다.
모두 1로 이루어졌을 경우 그 다음 숫자는 100..으로 시작하기 때문이다. 이는 비트의 차이가 많이 달라지기 때문에 정답과 주어진 숫자 사이의 차이가 커질 수 밖에 없다. 아마 모든 값을 반복하려고 하면 이 경우에서 시간을 가장 많이 써서 시간 초과가 나지 않을까 생각했다.
따라서 모두 1로 이루어졌을 경우 10을 붙이고 남은 자리를 1로 바꿔주는 방법을 사용했다.
numbers 배열의 길이만큼 위의 모든 과정을 반복하고 과정마다 answer 배열에 저장을 해준 뒤에 반환을 해주면 문제를 해결할 수 있다!
💡느낀 점
모든 과정을 반복해도 되는 문제와 모든 과정을 반복하지 않고 풀 수 있는 문제가 계속 헷갈린다. 어떤 문제들은 직접 반복을 해야 풀 수 있는데 괜히 규칙을 찾으려고 하다가 많은 시간을 쏟기도 하고 어떤 문제들은 반복 없이 풀 수 있는데 반복을 통해 풀다가 시간초과가 나기도 한다.. 여러 문제들을 풀어보고 있지만 아직까지도 어떤 문제에 어떤 것을 사용해야할지 생각하는 것은 어려운 것 같다..
링크
