프로그래머스 - 2개 이하로 다른 비트

leehyunjon·2022년 9월 4일

Algorithm

목록 보기

105/162

2개 이하로 다른 비트 : https://school.programmers.co.kr/learn/courses/30/lessons/77885

Problem

Solve

처음에 완탐으로 주어진 수 부터 1씩 늘려가며 비트로 바꾸고 다른 비트 개수를 새어서 찾는 식으로 구현했는데, 마지막 두개 테케에서 시간초과가 발생하였고 마땅한 방법이 떠오르지 않아 다른 코드를 참고하였다.

해당 문제를 풀때 유심히 봐야할 점이 있다.

첫번째, 이진수의 특징을 생각해봐야한다. 이진수는 짝수 일 때 1의 자리가 0이고 홀수 인경우 1의 자리가 1이게 된다.

두번째, 홀수인 경우 1로만 이루어진 이진수와 0이 포함된 이진수 두 경우로 나누어 볼 수 있다.

먼저 짝수, 홀수 여부를 파악하면
주어진 수가 짝수인 경우 1의 자리는 0이기 때문에 주어진 수에서 +1을 하게 되면 조건을 만족하는 수가 된다 (1개의 비트가 다르다)

그리고 홀수인 경우 1로만 이루어진 이진수와 0이 포함되어 이루어진 이진수가 있다.

먼저 1로만 이루어진 이진수일 경우 맨 앞자리에 1을 추가하고 다음 자리수를 0으로 변경한다면 두개의 비트가 다르고 주어진 수보다 크게 된다
- 예를 들어 7이 주어진 수일 때 이진수는 111 이게 된다. 맨 앞자리에 1을 추가하고 다음 자리수를 0으로 변경하면 1011 (11)이 된다.
0이 포함된 이진수인 경우 마지막에 있는 0의 자릿수를 찾아 1로 변경하고 다음 자리수를 0으로 변경해준다.
- 예를 들어 11은 이진수로 1011이 된다. 마지막 0인 자리수를 1로 변경하고 다음 자리를 0으로 변경한다면 1101 (13)이 된다. (1100 (12)는 3개의 비트가 다르기 때문에 안된다.)

위의 분기를 통해 조건을 만족하는 값을 반환해준다.

Code

class Solution {
    public long[] solution(long[] numbers) {
        long[] answer = new long[numbers.length];
		for (int i = 0; i < numbers.length; i++) {
			long number = numbers[i];

			//짝수라면 주어진 값 +1
			if (number % 2 == 0) {
				answer[i] = number + 1;
			} else {
            //홀수라면 1로만 이루어졌는데 0이 포함되는지 확인한다.
            	//이진수로 변경
				String binaryNumber = Long.toBinaryString(number);

				//변경된 이진수에 0이 포함되어있는지 확인
				int zeroLastIndex = binaryNumber.lastIndexOf("0");

				StringBuilder sb = new StringBuilder(binaryNumber);
				//1로만 이루어진 이진수 일때
				if (zeroLastIndex == -1) {
                	//sb를 뒤집어 맨 앞자리에 1을 추가하고 다시 뒤집어준다.
					sb.reverse().append("1").reverse();
                    //맨 앞자리 다음 위치인 1을 0으로 변경해준다. (주어진 값은 1이상이기 때문에 맨 앞에 1을 추가하면 2자리 이상이 된다)
					sb.setCharAt(1, '0');
				}
				//0이 포함된 이진수 일때
				else {
                	//마지막 0의 자리수를 1로 변경하고 다음 자리 1을 0으로 변경해준다.
					sb.setCharAt(zeroLastIndex, '1');
					if(zeroLastIndex+1<binaryNumber.length()) sb.setCharAt(zeroLastIndex+1, '0');
				}

				//이진수를 long타입 10진수로 변경
				answer[i] = Long.parseLong(sb.toString(), 2);
			}
		}

		return answer;
    }
}