[프로그래머스] 2️⃣ 2개 이하로 다른 비트 (JAVA)

🔗 문제 링크 

school.programmers.co.kr

 

---

⛈️  문제 설명 

양의 정수 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의 모든 수 ≤ 10

입출력 예

numbers	result
[2,7]	[3,11]

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

---

⛈️  풀이 과정

• 짝수 처리:
  • 짝수인 경우, 숫자에 1을 더하면(즉, number + 1) 비트 차이가 1인 가장 작은 큰 수가됨.
• 홀수 처리:
  • 홀수인 경우, 가장 오른쪽의 0을 찾아 그 0을 1로 바꾸고, 그 뒤의 1을 0으로 바꿔줌
  • *모든 비트가 1*인 경우(예: 111), 0이 없기 때문에, 맨 앞에 1을 추가하고 그 다음 비트를 0으로 바꿔줌

---

 

⛈️  대차게 틀린 코드  😇

가장 왼쪽에서 발견되는 1을 뒤에 ‘0’을 삽입하는 형태로 구현했으나,
모든 경우에 이 방식이 적용되는 것은 아님.
만약 비트가 더 복잡한 구조를 가지고 있는 경우,  예를 들어 11011 같은 경우라면,
가장 왼쪽의 1에만 의존하는 방식은 문제가 됨.

 

대차게 틀린 코드(전체)

 

import java.util.*;
/*
    ----- 💡도움 받음 ------
    
    <짝수> 
        1) 2를 2진수로 변환 : 10. 여기에 +1 -> 11이 됨. 11을 10진수로 변환 -> 3
        2) 4를 2진수로 변환 : 100. 여기에 +1 -> 101이 됨. 101을 10진수로 변환 -> 5
        
    <홀수>
        1) 1을 2진수로 변환 : 1. 
            여기에 1이 있는 가장 앞자리 바로 뒤에 0을 추가로 넣음 -> 10. 10을 10진수로 변환 : 2
        2) 7을 2진수로 변환 : 111. 
            여기에 1이 있는 가장 앞자리 바로 뒤에 0을 추가로 넣음 -> 1011. 1011을 10진수로 변환: 11

*/

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long [numbers.length];
        
        for (int i=0; i<numbers.length; i++){
            // 10진수 -> 2진수로 변환 (long타입)
            String num = Long.toBinaryString(numbers[i]);
            
            if (numbers[i]%2 == 0) { //짝수
                //  2진수에 +1을 한 뒤, 2진수를 다시 10진수로 변환
                // num = (Long.parseLong(num)+1)+"";    
                // answer[i] = Long.parseLong(num,2);
                
                answer[i] = numbers[i]+1; 
            }
            
            else { // 홀수 
                // 1이 처음에 나오는 바로 뒤에 0을 추가 
                StringBuilder sb = new StringBuilder(num);
                
                for(int t=0; t< num.length(); t++){
                    if (num.charAt(t) =='1'){
                        sb.insert(t+1, '0');
                        
                        //long타입의 10진수로 다시 변환
                        answer[i] = Long.parseLong(sb.toString(),2);
                    break;
                        }
                }
                
            }
            
            
        }
        
        
        
        return answer;
    }
}

 

  else { // 홀수 
                // 1이 처음에 나오는 바로 뒤에 0을 추가 
                StringBuilder sb = new StringBuilder(num);
                
                for(int t=0; t< num.length(); t++){
                    if (num.charAt(t) =='1'){
                        sb.insert(t+1, '0');
                        
                        //long타입의 10진수로 다시 변환
                        answer[i] = Long.parseLong(sb.toString(),2);
                    break;

 

---

⛈️  풀이 코드

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];

        for (int i = 0; i < numbers.length; i++) {
            long number = numbers[i];
            
            if (number % 2 == 0) {
                // 짝수는 +1만 하면 됨
                answer[i] = number + 1;
                
            } else {
                // 홀수 처리
                String num = Long.toBinaryString(number);
                StringBuilder sb = new StringBuilder(num);
                
                int lastZeroIndex = sb.lastIndexOf("0");

                if (lastZeroIndex != -1) {
                    // 가장 오른쪽에 있는 '0'을 '1'로 바꾸고, 그 다음 비트를 '0'으로 변경
                    sb.setCharAt(lastZeroIndex, '1');
                    sb.setCharAt(lastZeroIndex + 1, '0');
                } else {
                    // 모든 비트가 '1'인 경우, 맨 앞에 '1'을 추가하고 두 번째 자리에 '0'을 삽입
                    sb.insert(1, '0');
                }

                // 다시 10진수로 변환하여 저장
                answer[i] = Long.parseLong(sb.toString(), 2);
            }
        }

        return answer;
    }
}

 

---

 

☀️  한번 더 생각해 보자! 

📍 [JAVA] 10 → n진수로 변환, n → 10진수로 변환
📍 [JAVA] StringBuilder 사용과 주요 메소드
📍 [JAVA] Long → Integer, Integer → Long :: 타입 변환