프로그래머스 LV2. 2개 이하로 다른 비트 (자바)

🍀 문제

양의 정수 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]

 

 

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

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

 

 

😊 나의 코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            String bin = Long.toBinaryString(numbers[i]);
            int lastIndex = bin.lastIndexOf('0');
            String a = "";
            if(lastIndex==bin.length()-1) {
                a = bin.substring(0, lastIndex) + "1";
            }else if(lastIndex < 0){
                a = "10" + bin.substring(lastIndex + 2,bin.length());
            }else{
                a = bin.substring(0, lastIndex) + "10" + bin.substring(lastIndex + 2,bin.length());
            }
            answer[i] = Long.parseLong(a,2);
        }
        return answer;
    }
}

 

 

 

1. numbers의 숫자를 2진수로 변환 (long형 -> String형)

String bin = Long.toBinaryString(numbers[i]);

2. 변환한 2진수 값에서 마지막 0을 찾아 1로 바꿔줌

- 맨마지막이 0이면 그 0을 1로 바꿔줌

- 마지막 0이 없으면 맨앞 1을 10으로 바꿔줌 (ex : 111-> 1011)

- 그 외는 마지막 0과 그 바로 옆 1을 10으로 바꿔줌 (ex : 101 -> 110)

 

3. 바꿔준 2진수값을 다시 10진수의 long형으로 변환 후 answer에 담아줌

answer[i] = Long.parseLong(a,2)

 

 

👎 맨 처음 푼 코드 (시간초과로 실패)

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			long originNum = numbers[i];
			long biggerNum = originNum + 1;
			while (true) {
				String binary = Long.toBinaryString(originNum ^ biggerNum);
				if (binary.length() - binary.replaceAll("1", "").length() <= 2) {
					answer[i] = biggerNum;
					break;
				}
				biggerNum++;
			}

		}
		return answer;
    }
}

numbers의 숫자(originNum)와 점차 커지는 숫자(biggerNum)를 비교하면서

비트 차이가 2개 이하인 숫자를 answer에 담았다.

XOR을 사용해서 비트 차이가 얼마나 나는지 확인했는데,

2이하가 나올때까지 반복하는거라 시간초과가 난 것같다.

 

⭐ XOR 연산자 (^) -> 비트 차이가 나는 부분에 1을 반환

참고문서 👇

https://vmpo.tistory.com/106

[알고리즘] java 비트연산 정리하기