프로그래머스(자바, Java) - Level2. 2개 이하로 다른 비트

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

프로그래머스

---

문제리뷰 및 주요 포인트

• 입력받는 수의 범위는 0 ≤ numbers의 모든 수 ≤ 10¹⁵ 이다.
• 숫자 n을 입력받았을 때, 숫자에 1씩 더하고 자리 수를 맞춰주고 한 자리씩 추출해서 비교하도록 반복문을 사용했었다. 틀린 코드는 아니지만 시간초과가 발생했다.
• '질문하기'에서 시간초과에 대한 힌트를 얻고자 둘러보다 짝수는 2진수 변환 시 가장 끝자리 수가 항상 0 이기 때문에 +1을 하면 답이라는 것을 알게 되었다.
• 무작위 홀수들을 2진수로 변환하면서 일의 자리에 가까운 첫 번째 '01'이라는 숫자의 순서를 '10'으로 바꿔주면 된다는 법칙을 발견했다.
• 하지만 숫자 7과 같이 2진수로 변환했을 때 모든 수가 1인 경우 가장 앞자리에 0을 추가해줘야 한다.
• Ex) 111₍₂₎ > 0111₍₂₎

 

---

소스코드

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

        for(int i = 0; i < numbers.length; i++){
            answer[i] = bitCompare(numbers[i]);
        }

        return answer;
    }

    public long bitCompare(long num) {
        if (num % 2 == 0) {
            return num + 1;
        }
        // 10 -> 2
        String numToBi = Long.toBinaryString(num);

        // 모두 1인지 확인
        boolean same = true;
        for (int i = 0; i < numToBi.length() - 1; i++) {
            if (Character.compare(numToBi.charAt(i), numToBi.charAt(i + 1)) != 0) {
                same = false;
            }
        }

        // 모두 1이면 앞에 0 추가
        if (same) {
            numToBi = "0" + numToBi;
        }

        // 뒤에서부터 01 찾으면 바꿔주기
        char[] strArr = numToBi.toCharArray();
        for (int i = strArr.length - 1; i > 0; i--) {
            String str = String.valueOf(strArr[i - 1]) + String.valueOf(strArr[i]);
            if (str.equals("01")) {
                strArr[i - 1] = '1';
                strArr[i] = '0';
                break;
            }
        }

        String result = String.valueOf(strArr);

        return Long.parseLong(result, 2);
    }
}

 

 

 

채점결과

---