알고리즘/프로그래머스

프로그래머스 Lv.2) 다음 큰 숫자

Zin0_0 2020. 5. 19. 22:30
반응형

다음 큰 숫자

 

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

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니

programmers.co.kr

풀이

Lv2 문제를 풀고 있는 이유는 내 생각보다 생각을 많이 해야하는 문제가 존재하고, 기본을 다시 한 번 되돌아보기 좋기 때문이다. 또한, IDE를 사용하지 않고 문제를 푸는 연습을 하고있어서, 코드가 많이 길어지지 않는 문제들로 먼저 연습하고 있기 때문이다.

아무튼 이 문제를 처음 마주했을 때는 '이건 검색을 해야 알 수 있는 문제다' 였다. 물론 코드를 검색하고 이런 것이 아니라 JAVA에서 숫자를 2진수로 변경할 수 있는 메소드를 기본으로 제공해 줄 것 같았기 때문이다. 검색 결과 Integer에 toBinaryString(int num)이라는 메소드를 통해 제공하고 있었다. 물론 Long도 존재하겠지.. 아무튼, 이 문제는 2진수에 대한 이해도, 알고리즘에 대한 엄청난 이해도 요하지 않았다. 물론 더 효과적이고 짧은 코드를 생각해내자면 어렵겠지만, 문제를 푼다라는 입장에서만 봤을 때는 어렵지 않은 문제였다.

 

내가 푼 로직은 다음과 같다.

1. 입력받은 숫자 n 다음 자연수부터 1씩 증가하면서 while문을 돈다.

2. 비교대상이 될 숫자가 2진수로 변환했을 때, 입력받은 숫자 n의 2진수와 1의 개수가 같으면 while문을 종료하고 답을 return.

 

코드

public class NextBigNum_12911 {
    private static int solution(int n) {
        int cnt = getBinaryCnt(n);

        boolean isDone = false;
        int answer = n;
        while(!isDone) {
            if(getBinaryCnt(++answer) == cnt) {
                isDone = true;
            }
        }
        return answer;
    }

    private static int getBinaryCnt(int num) {
        int result =0;
        String str = Integer.toBinaryString(num);
        str = str.replaceAll("[0]", "");

        for(int i =0; i< str.length(); i++) {
            if(str.charAt(i) =='1') {
                result++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int n = 78;
        System.out.println(solution(n));
    }
}
반응형