[프로그래머스 level_2/월간 코드 챌린지 시즌 2] 2개 이하로 다른 비트 for JAVA

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

코딩테스트 연습 - 2개 이하로 다른 비트

[문제 설명]

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 1015

 

[풀이]

먼저 프로그래머스 기술 블로그의 글을 보며 풀이 방식에 아이디어를 얻은 점을 알린다.

https://prgms.tistory.com/57

 

해설에서 제시하는 문제풀이 방식은 간단하다.

 

1. 짝수면 가장 마지막에 있는 0을 1로 바꾼다. (1회 변환)

2. 홀수면 가장 마지막에 있는 0을 1로 바꾸고, 그다음 오는 1을 0으로 바꾼다. (2회 변환)

 

이 방식을 시각화하면 다음과 같다.

10진수	분류	2진수	변환한 2진수
10	짝수	1010	1011
12	짝수	1100	1101
13	홀수	1101	1110
7	홀수	111	1011

 

*주의할 점은 10진수 7에 해당하는 111은 앞에 0이 생략되있다는 사실을 생각하며 코딩으로 풀어야 한다.

애초에 0을 넣어주고 계산하는 것이 편하다

 

[코드]

 

/**
 * level 2 / 월간 코드 챌린지 시즌 2
 * 2개 이하로 다른 비트
 * https://programmers.co.kr/learn/courses/30/lessons/77885
 */
public long[] solution(long[] numbers) {
	
	long[] result = new long[numbers.length];
	
	for(int i = 0; i < result.length; i++) {		//각 요소 별로 처리
		result[i] = nextValueDifferentBit(numbers[i]);
	}
	
    return result;
}

public long nextValueDifferentBit(long number) {
	String binary = "0" + Long.toBinaryString(number);		//111 -> 0111
	StringBuilder result = new StringBuilder(binary);		//문자열 처리 편의성을 위해 StringBuilder를 사용
	
	int lastZeroIndex = result.lastIndexOf("0");			//처음 0인 부분을 찾음
	result.setCharAt(lastZeroIndex, '1');				//0을 1로 바꿔줌
		
	if(!isEvenNumber(number)) {					//number가 홀수면, 0 다음오는 1을 0으로 바꿔줌
		result.setCharAt(result.indexOf("1", lastZeroIndex + 1), '0');
	}
	
	return convertFromBinaryToDecimal(result.toString());
}

public boolean isEvenNumber(long number) {				//짝수 검증
	return number % 2 == 0 ? true : false;
}

public long convertFromBinaryToDecimal(String binary) {			//2진수 -> 10진수 치환
		return Long.parseLong(binary, 2);
	}
}

테스트 케이스 통과

 

느낀 점 : 오랜만에 느낀 점을 작성하는데... 일단 이 문제를 풀면서 최소한의 비트 변환으로 얻을 수 있는 최소의 수를 구하는 방법에 대해서 배우게 되었다. 아직 많이 공부해야 한다는 것을 느끼게 해 준다.

추가로 요즘 클린코드 책을 읽으면서 알게 된 점들을 코드에 녹이면서 코드를 작성하고 있다. 그게 레벨 2 문제라도...