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

개츠비·2023년 5월 17일

프로그래머스

목록 보기

13/16

소요시간 : 33분
문제 사이트 : 프로그래머스
문제 수준 : 레벨 2
문제 유형 : 푼 뒤 풀이를 봤는데 사람마다 푼 방법이 너무 다양했다.
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/77885
푼 날짜 : 2023.05.17

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘을 사용했다.

2. 사고과정

문제를 보고 1씩 더해준다면 시간 초과가 날 것이라고 생각했고,
그리디 알고리즘일 거라고 생각했다.

그래서 0부터 10정도까지 각각의 경우의 수를 계산해봄으로써 풀이를 알게 되었다.

예를들어
111001 의 경우는 변환한 것이 111011이다.
다른 경우도 살펴보자면, 우선 모든 수는 기본적으로
가장 오른쪽에 있는 0이 1로 변한다.

이것이 0~10까지의 수들을 변환하며 참인 것을 알아냈다.
그렇다면 숫자가 2개 변하는 경우는 어떤 경우인가?

그것은 가장 오른쪽에 있는 0이 1로 변한 후,
그 오른쪽의 인덱스부터 다시 탐색하며 1이 있다면 0으로 변한다.
예를 들어 보자.

10000111 을 보면, 가장 오른쪽의 0을 1로 변환시킨다.
10001111 이 될 것이다.
그 후 1로 변환시킨 그 오른쪽 인덱스부터 1을 찾고, 1이 있다면 0으로 변환시킨다.
10001011 이 될 것이다.

그 수가 x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수 가 된다.

✔️ 한 가지 예외가 있다. 바로 1111과 같이 1만으로 이루어진 숫자이다.
그 경우에는 0을 찾을 수 없다. 그렇다면 어떻게 해야 하는가 ?
간단하다. 1111 앞에 0을 붙여 01111 로 만들어 주고,
0 -> 1로 만들어 줌으로써 11111
1 -> 0로 만들어 줌으로써 10111

3. 풀이과정

숫자를 2진법 숫자로 변환.
앞서 말한 그리디 알고리즘을 적용. 이 때 숫자 앞에 "0"을 꼭 붙여준다. 1111의 예외를 방지하기 위함.
0의 인덱스와, 0다음의 인덱스 중 1의 인덱스를 찾았다면, 그 인덱스의 숫자들을 반전시켜서 배열에 담는다.

4. 소스코드

import java.io.*;
class Solution {
    public long[] solution(long[] numbers) {
        long[] answer=new long[numbers.length];
        
        for(int i=0;i<numbers.length;i++){
            String word=Long.toString(numbers[i],2);
            word="0"+word; //만약 1111이 입력인 경우에는 단 1개도 0으로 바꿀 수 없음.
            int idx1=-1;
            int idx2=-1;
            
            for(int j=word.length()-1;j>=0;j--){ //오른쪽에서부터 가장 가까운 0의 인덱스를 찾음
                if(word.charAt(j)-'0'==0){
                    idx1=j;
                    break;
                }
            }
  
            for(int j=idx1+1;j<word.length();j++){ //0의 인덱스보다 1 높은 인덱스부터 가장 가까운 1을 찾음
                if(word.charAt(j)-'0'==1){
                    idx2=j;
                    break;
                }
            }
        
            
            StringBuilder sb=new StringBuilder(word);
            sb.setCharAt(idx1,'1'); //0을 발견한 곳을 1로 바꿔줌.
            if(idx2!=-1){ // 1을 발견 못했다면 처리 X. 발견했다면 0으로 바꿔줌
                sb.setCharAt(idx2,'0');
            }
           
            
            answer[i]=Long.parseLong(sb.toString(),2); //10진법으로 변환
            
        }
       
        return answer;
    }
}