[77885] 2개 이하로 다른 비트

✔ 2개 이하로 다른 비트

[프로그래머스 77885]

문제 분석하기

x가 짝수일 경우와 홀수일 경우로 나누어 생각

x가 짝수일 경우에는 마지막 비트가 0이므로 1을 더하여 정답을 구함

x가 홀수일 경우에는 비트가 1로만 이루어진 홀수와 비트가 1과 0으로 이루어진 홀수가 존재하므로

1로만 이루어진 홀수일 때는 비트를 한 자리 더 추가해준 후 가장 작아져야 하므로 비트의 두 번째 자리를 0으로 변경해줌

1과 0으로 이루어진 홀수일 때는 가장 먼저 나오는 0을 1로 바꾸어주고, 그 다음 자리를 0으로 변경해줌

 

예1) 2 (10) → 3 (11)

예2) 7 (111) → 11 (1011)

예3) 5 (101) → 6 (110)

손으로 풀어보기

1. x가 짝수일 경우
   • 1을 더하여 정답을 구함
2. x가 홀수일 경우
   • 비트를 한 자리 더 추가해준 후 가장 작아져야 하므로 비트의 두 번째 자리를 0으로 변경하여 정답을 구함
     즉, "10" + 기존 비트의 두 번째 자리부터의 비트
   • 가장 먼저 나오는 0을 1로 바꾸어주고, 그 다음 자리를 0으로 변경하여 정답을 구함
     즉, 비트에서 0이 나오기 전까지의 기존 비트 + "10" + 비트에서 0이 나온 후와 그 다음 비트를 제외한 나머지 비트

슈도코드 작성하기

numbers(정수들이 담긴 배열)
answer(numbers의 모든 수들에 대하여 각 수의 f값)
for(i -> numbers의 길이만큼) {
    if(numbers[i]가 짝수라면)
        answer[i] = numbers[i] + 1
    else {
        convertNum(numbers[i]를 이진수로 변환한 수)
        index(가장 먼저 0이 나오는 인덱스)
        if(index가 -1이라면) {
            비트에 0이 존재하지 않으므로 convertNum를 "10" + 기존 비트의 두 번째 자리부터의 비트로 갱신
            answer[i] = convertNum을 십진수 Long형으로 변환한 수를 저장
        }
        else {
            비트에 0이 존재하므로 convertNum를 비트에서 0이 나오기 전까지의 기존 비트 + "10" + 비트에서 0이 나온 후와 그 다음 비트를 제외한 나머지 비트로 갱신
            answer[i] = convertNum을 십진수 Long형으로 변환한 수를 저장
        }
    }
}
answer 변환

코드 구현하기

/**
 * 77885) 2개_이하로_다른_비트
 */
public class L066_77885 {
    // numbers(정수들이 담긴 배열)
    public long[] solution(long[] numbers) {
        // answer(numbers의 모든 수들에 대하여 각 수의 f값)
        long[] answer = new long[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            // numbers[i]가 짝수라면
            if (numbers[i] % 2 == 0)
                // numbers[i] + 1을 저장
                answer[i] = numbers[i] + 1;
            // numbers[i]가 홀수라면
            else {
                // convertNum(numbers[i]를 이진수로 변환한 수)
                String convertNum = Long.toBinaryString(numbers[i]);
                // index(가장 먼저 0이 나오는 인덱스)
                int index = convertNum.lastIndexOf("0");
                // 비트에 0이 존재하지 않는다면
                if (index == -1) {
                    // convertNum를 "10" + 기존 비트의 두 번째 자리부터의 비트로 갱신
                    convertNum = "10" + convertNum.substring(1, convertNum.length());
                    // convertNum을 십진수 Long형으로 변환한 수를 저장
                    answer[i] = Long.parseLong(convertNum, 2);
                }
                // 비트에 0이 존재한다면
                else {
                    // convertNum를
                    // 비트에서 0이 나오기 전까지의 기존 비트 + "10" + 비트에서 0이 나온 후와 그 다음 비트를 제외한 나머지 비트로 갱신
                    convertNum = convertNum.substring(0, index) + "10"
                            + convertNum.substring(index + 2, convertNum.length());
                    // convertNum을 십진수 Long형으로 변환한 수를 저장
                    answer[i] = Long.parseLong(convertNum, 2);
                }
            }
        }
        // answer 변환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L066_77885 solution = new L066_77885();

        long[] numbers = { 2, 7 };

        long[] result = solution.solution(numbers);

        System.out.println(Arrays.toString(result));
    }
}