[알고리즘 스터디 2주 차(1)] 다음 큰 숫자

 

프로그래머스

 

 

class Solution {
    public int solution(int n) {
        
        int answer = 0; 
        
        String str = Integer.toBinaryString(n);
        int cnt = 0;
        
        for(int i=0; i<str.length();i++){
            if(str.charAt(i)=='1')
                cnt++;
        }
        
        for(int i=n+1;i<1000000;i++){
            
            String temp = Integer.toBinaryString(i);
            int temp_cnt = 0;
        
            for(int j=0; j<temp.length();j++){
                if(temp.charAt(j)=='1')
                temp_cnt++;
            }   
            
            if(temp_cnt == cnt){
                answer = i;
                break;
            }
        }

        return answer;
    }
}

 

풀이 1

Integer.bitCount();
정수를 매개변수로 넣었을때 그 정수의 1 의 개수를 반환한다.

 

class Solution {
    public int solution(int n) {
        
        int nc = Integer.bitCount(n);
        System.out.println(nc);
        
        for(int i = n+1;;i++){
            int nc2 = Integer.bitCount(i);
            if(nc == nc2) return i;
        }
    }
}

위의 코드는 문제 풀이에서는 이상이 없지만, 효율성 테스트에서는 시간 초과가 된다.

 

 

풀이 2

Integer.toBinaryString(n)
java.lang패키지에 있는 Integer클래스는10진수 값을 2진수로 바꾸고 2진수를 10진수로 바꿔준다.

 

class Solution {
    public int solution(int n) { // n == 15
        int nc = countBits(n); 
        while(nc != countBits(++n)); // 15의 2진수의 개수인 4가 n+1의 2진수의 개수와 같지 않을 때까지 무한 반복을 돌린다. == 만약 같으면 반복문이 종료된다.
        System.out.println("여기서 nc의 개수 : "+nc); // 15의 다음 큰 수는 23인데, 그 이유는 23의 2진수는 10111로 1의 개수가 4이기 때문이다.
        return n; //  따라서 반복문 종료되고 n의 값을 return한다.
    }
    
    private int countBits(int n){
        String strN = Integer.toBinaryString(n); // 15를 2진수로 변환한 값(=1111(2))을 strN에 담는다.
        System.out.println("다음 숫자 : " + strN); 
        int nc = 0; // 1의 개수를 셀 변수인 nc를 0으로 초기화한다.
        for(char ch : strN.toCharArray()) if(ch == '1') nc++; // strN.toCharArray()를 이용해서 ch에 1이라는 문자가 있다면 nc를 1씩 증가시킨다. 
        System.out.println("nc의 개수 : "+nc);
        return nc; // nc(=1의 개수)를 반환한다.
    }
    
}