[코딩테스트 연습] 다음 큰 숫자 - Lv.2

[문제]

다음 큰 숫자 - Lv.2

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

프로그래머스

---

 

[문제 풀이]

처음 접근했던 방법은 n을 이진수로 변환해서 1의 개수(cnt)를 저장한 뒤, while 반복문을 사용해서 n을 1씩 증가시켜 똑같이 이진수로 변환하고 1의 개수(reCnt)를 저장한 뒤에 cnt와 reCnt가 같을 때, 반복문을 종료하여 정답을 찾았다. 

이렇게 코드를 작성했을 때 시간 복잡도는 O(n^2)로 당연히 시간 초과가 날 것으로 예상했다. 

이중 반복문을 해결해야 정답으로 넘어갈 수 있다고 생각했다. 

구글링 결과 Integer.bitCount() 메서드를 찾았다. 

정수를 이진수로 변환했을 때 1의 개수를 반환해주는 메서드이다. 

이 메서드를 적용하니 시간 초과 문제가 바로 해결되었다. 

---

 

[코드]

class Solution {
    public int solution(int n) {
        int answer = 0;
        int cnt = Integer.bitCount(n);
        
        while(true) {
            int reCnt = Integer.bitCount(++n);
            
            if(cnt == reCnt) {
                answer = n;
                break;
            }
        }
        
        return answer;
    }
}

 

 

2023.09.26