다음 큰 숫자 (프로그래머스) [JAVA]

 

문제

문제 링크 : 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 이하의 자연수 입니다.

입출력 예

n	result
78	83
15	23

 

풀이

처음엔 1이 몇개일때, 0이 몇 개일때 룰을 생각해보았지만 쉽지 않았다.
자연수 n이 주어졌을때, 생각할 수 있는 1의 개수가 같은 자연수는 2*n이므로
이 사이에 있는 수들을 일일히 완전탐색해보면 될 것 같다고 생각했다
자연수 n을 이진수로 변환하면 길이가 $lgn$이 되므로
이를 n+1 ~ 2n까지 n번 검사하기 때문에 시간복잡도는 $O(nlgn)$ 이라 생각한다.

 

코드

class Solution {
    public int solution(int n) {
        String sub;
        int count = find1(Integer.toBinaryString(n));
        //System.out.println(count);

        for(int i=n+1; i<2*n+1; i++){
            sub = Integer.toBinaryString(i);    //2진수 string으로 변환
            int s = find1(sub);
            if(s == count){
                //System.out.println(i + " " +sub);
                return i;
            }
        }

        int answer = 0;
        return answer;
    }
    public int find1(String s){
        int count = 0;
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '1') count++;    //일일히 1의 개수 세기
        }
        return count;
    }
}

 

 

결과

정확성 테스트
테스트 1 〉 통과 (0.83ms, 42.6MB)
테스트 2 〉 통과 (0.87ms, 42.6MB)
테스트 3 〉 통과 (0.90ms, 42.4MB)
테스트 4 〉 통과 (0.80ms, 42.3MB)
테스트 5 〉 통과 (0.91ms, 42.6MB)
테스트 6 〉 통과 (0.77ms, 42.3MB)
테스트 7 〉 통과 (0.82ms, 42.8MB)
테스트 8 〉 통과 (0.77ms, 42.9MB)
테스트 9 〉 통과 (0.60ms, 42.9MB)
테스트 10 〉통과 (0.84ms, 43MB)
테스트 11 〉통과 (0.87ms, 42.6MB)
테스트 12 〉통과 (0.84ms, 42.3MB)
테스트 13 〉통과 (0.83ms, 42.6MB)
테스트 14 〉통과 (0.73ms, 42.9MB)