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

문제

https://programmers.co.kr/learn/courses/30/lessons/12911?language=java 

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

 

풀이

'n의 다음 큰 숫자' 조건에 부합하는 수를 구하라.

1. n의 다음 큰 숫자는 n보다 큰 자연수이다.
2. n의 다음 큰 숫자는 n의 2진수로 변환했을 때 1의 갯수가 같다. (ex: 1101 -> 1110 : 1이 3개)
3. 위 두 조건을 만족하는 수 중 가장 작은 수
4. 이 때, n은 1,000,000 이하의 자연수

 

접근 방식

조건을 만족하는 수 중 가장 작은 수를 반환해야 하므로, n보다 큰 값들에 대해 차례대로 접근하면서(조건1, 조건3 무조건 만족) 조건2 부합 여부를 체크해 나가자. 조건 2에 부합하는 순간 그 값을 바로 반환.

조건2를 체크하기 위해서 n값의 2진수에서 1의 개수를 미리 구해둔다.

코드

class Solution {
    public int solution(int n) {
        int answer = n + 1;		// n 다음 값부터 시작
        int cntOne = 0;
        // 진수 변환
        String binaryNum = Integer.toBinaryString(n);
        // 이진수에서 1의 개수
        for (String s : binaryNum.split("")) {
            if(s.equals("1"))
                cntOne++;
        }

        while (true) {
            String binaryNum2 = Integer.toBinaryString(answer);
            int cntOne2 = 0;
            for (String s : binaryNum2.split("")) {
                if(s.equals("1"))
                    cntOne2++;
            }

            if (cntOne2 == cntOne) {
                break;
            } else {
                answer++;
            }
        }

        return answer;
    }
}

 

• 처리 로직
  • n을 이진수 문자열로 변환
  • 이진수 문자열에서 "1"의 개수를 카운트
  • n+1 값 부터 차례대로 이진수 변환 -> "1"개수 카운트 반복
  • 이진수 일 때 1의 개수가 'n이 이진수일 때 1의 개수'와 같은 값이 나오면 반복 종료, 해당 값 반환

 

위와 같이 코드를 짜고 실행하면, [정확성 테스트]에는 통과하나, [효율성 테스트]에서 시간 초과로 실패가 뜨게 된다.

 

이진수 문자열을 String[] 배열로 변환해 "1"의 개수를 카운트 하는 부분이 시간초과의 원인이라고 생각해 이진수에서 1의 개수를 세는 방식을 변경하였다.

 

코드 개선

n보다 큰 수를 저장하는 변수, 이진수에서 1의 개수를 세는 방식을 수정하였다.

• 기존 코드
  • n의 이진수 문자열(String)의 각 요소를 .equals("1") 메서드로 비교하는 식으로 1의 개수 카운트
  • n 보다 큰 수에 차례로 접근하기 위해 answer값을 n+1로 초기화해서 사용
• 개선 코드
  • n 자체에 Integer.bitCount() 메서드를 사용해 1의 개수 카운트
  • n의 이진수에서 1의 개수를 구한뒤에는 n값이 필요없기 때문에, n보다 큰 수를 접근하기 위한 용도의 변수로 n자체를 사용

 

class Solution {
    public int solution(int n) {
        int cntOne = Integer.bitCount(n);
        
        while (true) {
            n++;    // n보다 큰 수 차례로 접근
            if (cntOne == Integer.bitCount(n)) {
                return n;
            }
        }
    }
}

수정한 코드는 [효율성 테스트]에 모두 통과하였다.

 

Integer.bitCount()

매개변수로 정수를 전달하면, 그 정수가 이진수일 때 1의 개수를 반환한다.
ex) 15 -> 1111 -> 4,  9 -> 1001 -> 2