[프로그래머스][Java] Lv.2 다음 큰 숫자

 

풀이과정

1. n을 이진수로 바꾸면서 1의 개수를 센다.
2. n을 1씩 증가하면서 입력으로 주어진 n과 1의 개수가 같아질 때까지 찾는다.

 

코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int one = cntOne(n); //초기 n의 1개수.
        
        //1의 개수가 같을 때까지 n++하면서 조사.
        while(true){
            n++;
            if(cntOne(n)==one){
                answer=n;
                break;
            }
        }
        return answer;
    }
    //n을 이진수로 바꿨을 때 1의 개수
    static int cntOne(int n){
        int cnt=0;
        while(n>1){
            cnt+=n%2;
            n/=2;
        }
        return ++cnt; //제일 앞자리 1
    }
}

---

다른사람 풀이

cntOne해주는 함수를 따로 만들 필요 없이 Integer내장함수인 Integer.bitCount를 사용하면 훨씬 더 쉽게 풀이 가능하다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        int one = Integer.bitCount(n); //이진수로 바꿨을 때 1의 개수 count
        
        //1의 개수가 같을 때까지 n++하면서 조사.
        while(true){
            n++;
            if(Integer.bitCount(n)==one){
                answer=n;
                break;
            }
        }
        return answer;
    }
}

---

효율성 오류

while(true){
	n++;
	int one = Integer.toBinaryString(n).replaceAll("0","").length();
}

처음 알고 있는 함수를 활용해보려고 replace함수를 사용하였는데,

replace함수는 문자열 처음부터 검색하는 함수이므로 while문 안에 넣게 되면 시간복잡도가 O(n^2)로 크게 증가한다

이 부분에서 효율성 오류가 나지 않았을까 싶다.