[프로그래머스_Level2] 다음 큰 숫자

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

코딩테스트 연습 - 다음 큰 숫자

[문제]

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

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

 

 예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다. 자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

 

[제한 조건]

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

 

[코드]

class Solution {
    public static int solution(int n) {
        int answer=0;
        // n을 2진수로 바꾸기
        String str=Integer.toBinaryString(n);
        int count=0;
        
        // n을 2진수로 바꾼 값에서 1의 개수를 count한다.
        for(int i=0;i<str.length();i++)
        	if(str.charAt(i)=='1')
        		count++;
        
        // 완전 탐색
        for(int i=n+1;i<1000000;i++) {
        	// n보다 큰 수를 2진수로 변환
        	String num=Integer.toBinaryString(i);
        	int one_count=0;
        	
        	// 1의 개수 count
        	for(int j=0;j<num.length();j++)
        		if(num.charAt(j)=='1')
        			one_count++;
        	
        	/*
        	 * n과 1의 개수가 같다면 해당 값을 저장 후 
			 * 조건을 만족하는 가장 작은 값을 찾는 것이기 때문에 break
        	 */
        	if(one_count==count) {
        		answer=i;
        		break;
        	}
        }
        return answer;
	}
}

 

[고찰]

 이번 문제의 핵심은 2진수로 변환하는 함수를 사용해야 한다는 것과 완전탐색을 통해 조건을 만족하는 값을 찾아내는 것이다.

 처음에는 10진수를 2진수로 변환하는 과정을 직접 구현했지만 코드가 길어지고 복잡해져 라이브러리 함수를 사용하였다. 그리고 조건을 만족하는 수를 구하기 위해 주어진 n을 2진수로 바꾼뒤 자릿수 처음과 가장 가까운 0을 1로 바꾸고, 1을 0으로 바꾸는 알고리즘을 생각했다. 하지만 이렇게 하면 구한 수가 n보다 큰 값이 아닐수 있기 때문에 n보다 큰 값들 중 조건을 만족하는 값을 완전탐색으로 알아내야 한다는 것을 알았다.