[프로그래머스] 다음 큰 숫자 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 개수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

2. 입력

• n은 1,000,000 이하의 자연수입니다.

3. 예제

N	Result
78	83
15	23

4. 풀이

제가 이 문제를 푼 방법은 입력으로 받은 N에 사칙 연산을 하면 풀 수 있을 것 같았습니다.

 

먼저 2진수의 가장 오른쪽부터 시작하여 연속되는 1의 가장 왼쪽의 Index와 1의 개수를 구합니다.

 

그다음은 N의 홀수 짝수 여부에 따라 규칙이 달라지게 됩니다.

• N이 홀수인 경우
  N에 2^Index(오른쪽부터 시작하여 연속되는 1의 가장 왼쪽의 Index)만큼 뺀 뒤
  위에서 구한 N 값에 2^Index+1을 한 값을 다시 더하는 것입니다.
  최종적으로 N - 2^Index + 2^Index+1이 비트수가 같은 N보다 큰 수들 중 가장 작은 값이 됩니다.
  
  홀수의 경우 가장 오른쪽 비트는 무조건 1이 되게 됩니다.
  여기서 N보다 큰 수를 만들기 위해 1을 더하면 오른쪽에서부터 연속된 1은 모두 0으로 바뀌고 연속이 끝나는 0이 1로 변경 되게 됩니다.
  즉 100111에서 1을 더하면 -> 101000으로 변경됨
  위 와 같이 1을 더한 2진수에서 비트수가 같게 만들면서 가장 작은 수는 오른쪽부터 1을 채워 나가는 방법입니다.
  

  1개	101001
  2개	101011

  남은 2개의 1을 오른쪽 부터 채워 나가면 101011이 되게 됩니다.
  최초 입력 N의 2진수 100111과 최종 결과 101011은 N - 2^Index + 2^Index+1이 되게 됩니다.
  
• N이 짝수인 경우는 연속된 1이 1개인 경우 연속된 1이 2개 이상인 경우로 구분됩니다.
  
  
• N이 짝수이면서 연속된 1이 1개인 경우
  이 경우는 홀수와 동일하게 구할 수 있습니다.
  
  
• N이 짝수이면서 연속된 1이 2개 이상인 경우
  N에 2^Index(오른쪽부터 시작하여 연속되는 1의 가장 왼쪽의 Index) - 1만큼 뺀 뒤
  위에서 구한 N 값에 2^Index+1을 한 값을 다시 더하고 마지막으로 1을 더하는 것입니다.
  최종적으로 N - 2^(Index-1) + 2^(Index+1) + 1이 비트수가 같은 N보다 큰 수들 중 가장 작은 값이 됩니다.
  
  짝수의 경우 가장 오른쪽 비트는 무조건 0이 되게 됩니다.
  여기서 N보다 큰 수를 만들기 위해 1을 더하면 가장 오른쪽 비트 0이 1로 변경되며 1의 개수가 1개 증가하게 됩니다.
  이제 1개 많아진 1을 다시 줄이기 위해 연속된 1중 가장 오른쪽을 지우면 다시 수는 N보다 작은 수가 되게 됩니다.
  결국 연속된 1을 그냥 지워서는 안 되므로 연속된 1의 가장 왼쪽의 1을 한 칸 왼쪽으로 옮기고 이전 자리는 0으로 변경합니다.
  

  10110

  11010

  위 표처럼 10110을 11010으로 변경하면 1의 개수는 같지만 가장 작은 수가 아닙니다.
  

  변경된 수	작은 수
  11010	11001
  11010	11010
  11010	11100

  이유는 이미 연속된 1의 가장 왼쪽의 비트가 한 칸 이동을 하였으므로 이후 비트 자리는 어디를 와도 N보다는 큰수가 됩니다.
  그러므로 가장 작은 수를 만들기 위해 Index위치에서 한칸 오른쪽의 비트 또한 0으로 변경한 뒤 가장 오른쪽 비트는 1로 변경하는 것이 가장 작은 수가 됩니다.

해당 문제는 입력으로 받은 N을 1씩 증가시키면서 해당 숫자의 BitCount를 Check 하여 같으면 해당 값을 Return을 해도 정답이 되는 것 같습니다.

5. 코드

전체 코드는 Git에 있습니다.

StringBuilder number = new StringBuilder(Integer.toBinaryString(n)).reverse().append('0');

int mOneCnt = 0;
int oneIndex = -1;
for(int i=0; i<number.length()-1; i++){
	if(number.charAt(i) == '1'){
		mOneCnt++;
		if(number.charAt(i+1) == '0') {
			oneIndex = i;
			break;
		}
	}
}

if ((n & 1) == 1) {
	n -= (int) Math.pow(2, oneIndex);
	n += (int) Math.pow(2, oneIndex + 1);
}
else{
	n -= (int) Math.pow(2, oneIndex);

	if(mOneCnt >= 2){
		n -= (int) Math.pow(2, oneIndex - 1);
		n += (int) Math.pow(2, oneIndex + 1);
		n++;
	}
	else{
		n += (int) Math.pow(2, oneIndex + 1);
	}
}

return n;