프로그래머스 | LV.2 2개 이하로 다른 비트 - 구현 문풀 (Java)

⬛ 프로그래머스 | LV.2 2개 이하로 다른 비트 - 구현 문풀 (Java)

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

프로그래머스

 

문제 설명

---

💚문제 접근 방식

처음에 든 풀이법은 while 문으로 주어진 배열 값 각각을 1씩 증가시켜 비트와 주어진 수를 비교하다가 다른 비트가 2개 이하면 break; 걸어주어서 개수를 리턴하는 단순한 방식이었다. 그런데 이 방식은 시간초과가 난다. 제한사항에서 numbers의 모든 수가 10^15이하이기 때문에 더 효율적인 풀이 방법을 생각해내야 한다.  

내 힘으로 완전히 해결을 못했고, 비트의 패턴 규칙성을 토대로 문제를 푼 코드를 참고했다.

 

1) 일단 짝수인 경우, 2진수 상의 1의 자리 비트에 1더한 값이 반드시 답이 된다.

2) 홀수라면 비트 끝부터 탐색하여 0이 나온 지점에 ‘10’ 비트를 넣어주면 답이 된다. (→ 만약 0인 지점이 없다면 맨 앞에 10을 붙여줌)

 

💚 제출 코드

import java.util.*;

class Solution {
    //솔루션 함수 
    public List<Long> solution(long[] numbers) {
        List<Long> answer = new ArrayList<>();
        
        for(long num : numbers){
            String target = Long.toBinaryString(num);//이진수 변환 
            
            if(num % 2 == 0){ //현재 수가 짝수
                //1더한 값을 변환한 게 정답
                answer.add(num+1);
            }else{ //현재 수가 홀수 
                int idx = target.lastIndexOf("0");
                if(idx == -1){//없다면 맨 앞에 10 붙임
                    String tmp = "10" + target.substring(1, target.length());
                    answer.add(Long.parseLong(tmp, 2));  //2진수를 정수로 변환 
                }else{
                    String tmp = target.substring(0, idx) + "10" + target.substring(idx+2, target.length());
                    answer.add(Long.parseLong(tmp, 2)); //2진수를 정수로 변환 
                }  
            }            
        }
        return answer;
    }
}