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

문제 링크

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

프로그래머스

---

💡 아이디어

numbers의 길이가 최대 100,000이고, numbers의 모든 수는 최대 10^15까지도 나올 수 있기 때문에 

평소처럼 x를 1씩 늘리면서 해당 값이 f(x)인지 확인하면 정확성 테스트 10,11에서 시간초과가 납니다.

 

따라서 질문하기에 힌트를 보고 참고해 문제를 풀었습니다.

 

숫자가 짝수인 경우와 홀수인 경우를 나눠서 문제를 해결했습니다.

1. 만약 숫자가 짝수라면 이진수로 바꿨을 때 마지막 자릿수가 0일 것이므로 마지막 자리를 1로 바꿔주기만 하면 f(x)를 구할 수 있습니다.
ex) 2 : 10 => 11 : 3

 

2. 만약 숫자가 홀수라면 맨 뒷자리부터 가장 먼저 0이 나오는 위치를 찾아 1로 바꿔주고, 최대 2자리를 바꿀 수 있으므로 x보다 큰 수중에 가장 작은 수를 만들기 위해 0이 나오는 위치 뒤에 1을 찾아 0으로 바꿔줍니다.

ex) 13 : 1101 => 1111 => 1110 : 14

---

📖 풀이과정

1. numbers의 숫자를 하나씩 받아와서 연산을 수행합니다.

 

2. 만약 numbers[i]가 짝수라면 이진수로 변환했을 때 마지막 자릿수가 0이기 때문에 마지막 자릿수에 1을 더한 값인 numbers[i]+1을 정답배열에 넣어주고 다음 반복문을 실행합니다.

if(numbers[i]%2==0){
	answer[i] = numbers[i]+1;break;
}

 

3. 만약 홀수라면, 일단 numbers[i]를 이진수로 변환합니다.

String bin = Long.toString(numbers[i],2); //이진수로 변환하는 함수

 

4. f(x)를 구하기 위해 f(x)를 담아놓을 StringBuilder를 선언합니다.

( * String으로 선언하면 index의 문자를 바꾸기 어렵기 때문에 setCharAt함수를 사용하기 위해 StringBuilder로 선언한다.)

StringBuilder next = new StringBuilder(); //f(x)

 

5. 들어온 x의 이진수의 맨 뒷자리 부터 제일 처음 0이 나오는 지점을 찾습니다.

( 0이 하나도 없는 경우를 고려하기 위해 처음 zeroIdx초기화를 bin의 길이로 합니다.)

long zeroIdx = bin.length(); //뒤에서부터 가장 먼저 나오는 0 index

for(long j=bin.length()-1;j>=0;j--){
    if(bin.charAt((int)j)=='0'){
    	zeroIdx=j;break;
    }
}

 

6. zeroIdx의 0을 1로 바꿔주고, 만약 0이 하나도 없는 경우라면 맨 앞자리에 1을 추가해 줍니다.

if(zeroIdx==bin.length()){//0이 하나도 없는 경우
    next.append("1"+bin); //맨 앞자리에 1 추가
    zeroIdx=0;//바꿔준 자리 저장
}
else{
    next.append(bin);//next에 bin을 그대로 넣어주고
    next.setCharAt((int)zeroIdx, '1'); //zeroIdx만 0->1로 바꾼다
}

 

7. x보다 큰 숫자 중 가장 작은 수를 만들기 위해, 숫자를 바꿔준 zeroIdx 뒤부터 가장 먼저 만나는 1을 0으로 바꿔줍니다.

for(int j=(int)zeroIdx+1;j<next.length();j++){
    if(next.charAt(j)=='1'){
    	next.setCharAt(j,'0');break;
    }
}

 

8.  구한 next를 String형으로 바꿔 answer에 넣어주고, numbers의 배열 모두 2-7번 작업을 반복합니다.

 

---

전체 코드

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
        
        for(int i=0;i<numbers.length;i++){
        	
        	// 10-> 11 : 1의 자리가 0이므로 그 자리만 바꿔주면 i번째 수보다 크면서 가장 작은수
        	if(numbers[i]%2==0) {
        		answer[i]=numbers[i]+1;continue;
        	}
            String bin = Long.toString(numbers[i],2);//numbers[i]를 이진수로 변환.
            
            StringBuilder next= new StringBuilder(); //f(x)
            
            long zeroIdx=bin.length();//뒤에서부터 0이 나오는 지점 찾기
            for(long j=bin.length()-1;j>=0;j--) {
            	if(bin.charAt((int) j)=='0') {
            		zeroIdx=j;break;
            	}
            }
            //뒤에서부터 가장 먼저 나온 0을 1로 바꿔준다.
            if(zeroIdx==bin.length()) {//1로만 이뤄져 있을 경우.
            	next.append("1"+bin);
            	zeroIdx=0;
            }
            else{
            	next.append(bin);
            	next.setCharAt((int)zeroIdx, '1');
            }
            //zeroIdx 뒤부터 가장 가까운 1을 0으로 바꾸기
            for(int j=(int)zeroIdx+1;j<next.length();j++) {
            	if(next.charAt(j)=='1') {
            		next.setCharAt(j, '0');break;
            	}
            
            //System.out.println(next);
            answer[i]=Long.parseLong(next.toString(),2);
            
        }
        
        return answer;
    }
}