2개 이하로 다른 비트 / 자바 / 프로그래머스

문제         

프로그래머스

 

1 번째 시도   

완전탐색을 시도하려다가 numbers의 길이를 보고 시간초과를 직감하여 완전탐색은 포기하였습니다.

이런경우 규칙을 찾는 것이 중요합니다. 완전탐색으로 시간초과가 나는 경우 출제자들이 무조건 규칙을 만들어놓습니다.

제가 찾은 규칙은 이렇습니다.

 

1.  가장 끝에서 0인 숫자를 1로 바꾼다. 뒤에 숫자를 0으로 바꾼다.

2. 0이 binary 맨 뒤에 있는 경우 0 -> 1만 해준다.

3. 0이 존재하지 않는 경우 1을 추가하고 기존 맨 앞 숫자를 1 -> 0으로 바꿔준다.

import java.util.*;

class Solution {
    public long[] solution(long[] numbers) {

        String[] ns = new String[numbers.length];
        Long[] result = new Long[numbers.length];
        
        for(int i =0; i < numbers.length; i++) {
            ns[i] = Long.toBinaryString(numbers[i]);
        }
        
        for(int i = 0; i < numbers.length; i ++) {
            int binaryIndex = ns[i].length()-1;
            
            if(ns[i].charAt(binaryIndex) == '0') {
                 ns[i].charAt(binaryIndex) = "1";
            } 
            else {
                while(ns[i].charAt(binaryIndex) != 0) {
                    binaryIndex--; 
                }
                ns[i].charAt(binaryIndex) = "1";
                ns[i].charAt(binaryIndex+1) = "0";
            }
            
            result[i] = Long.parseLong(ns[i], 2);
        }
        
        return result;
    }
}

 

charAt으로 String을 바꾸려고했지만,  Java의 문자열은 변경할 수 없기 때문에 불가능합니다. charAt(index)를 사용하여 문자에 새 값을 할당하여 문자를 직접 변경할 수는 없습니다. 대신 StringBuilder를 사용하거나 원하는 변경 내용으로 새 문자열을 구성해야 합니다.

 

2 번째 시도  

 

import java.util.*;

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

        for (int i = 0; i < numbers.length; i++) {
            String binary = Long.toBinaryString(numbers[i]);
            StringBuilder sb = new StringBuilder(binary);

            int lastZero = sb.lastIndexOf("0");
            if (lastZero == binary.length() - 1) {
                sb.setCharAt(lastZero, '1');
            } else if (lastZero == -1) {
                sb.insert(0, "1");
                sb.setCharAt(1, '0');
            } else {
                sb.setCharAt(lastZero, '1');
                sb.setCharAt(lastZero + 1, '0');
            }

            result[i] = Long.parseLong(sb.toString(), 2);
        }

        return result;
    }
}