[200804] 다음 큰 숫자 - 연습문제(level2)

1. 문제 이해

다음 조건을 만족하는 n의 다음 큰 숫자 구하기

조건1) n보다 큰 자연수
조건2) 2진수 변환 시 1의 갯수가 같다.
조건3) 조건1, 조건2를 만족하는 수 중 가장 작은 수

2. 전략

(풀이1) 규칙 이용

1)  이진수 형태의 string으로 변환 : Integer.toBinaryString(int n)
2) 뒤에서 처음 발견되는 "0"(lastZero), "1"(lastOne)의 인덱스 구하기 : lastIndexOf(String str)

** 가장 마지막에 오는 "01"을 찾는 것이 목표
** String one = "1" --> string의 곱하기 연산이 안되므로 repeat 이용 : one.repeat(횟수)
** size : n의 이진수 형태의 길이(전체 길이) / count : n의 이진수 중 1의 개수 = (n_str.replace("0", "")).length()
3) lastOne < lastZero(맨 뒤 숫자가 0인 경우) : 다음 0의 위치 구하기
4) lastZero == -1 (0이 없는 경우) : 자릿수를 증가시켜줌.
    "1" +  zero.repeat(size-count+1) + one.repeat(count
5) lastOne > lastZero ("01"을 찾은 경우) : 0을 1로 변환, 앞은 그대로 두고 뒤의 나머지 1은 개수에 맞춰 뒤에서부터 채움
    n_str.substring(0, lastZero) + "1" + zero.repeat(size-lastOne) + one.repeat(lastOne-lastZero-1)

- 문제점 : 시간 효율성 테스트 불합격

 

(풀이2) n을 1씩 증가시키면서 1비트의 수를 비교

1 비트의 수를 카운트하는 방법이 필요

1) Integer 클래스의 bitCount(int n) : n의 2진수(binary) 데이터 중 1 비트의 수를 카운트

2) int calcBit(int n) 함수 만들기

int calcBit(int n){
    String s = Integer.toBinaryString(n);
    return (s.replace("0", "")).length();
}

 

3. 참고사항

1) String 클래스의 메소드

- repeat(int n) : String을 n번 반복

- replace(String s1, String s2) : String의 s1을 s2로 대체

- substring(int a, int b) : String의 a~b-1번째 인덱스까지 자른 string

- IndexOf(String s), lastIndexOf(String s) : 앞/뒤에서 부터 s가 처음으로 나타나는 인덱스

 

2) Integer 클래스의 메소드

- toBinaryString(int n) : n을 2진수 형태로 바꾼 string

- bitCount(int n): n의 2진수 데이터 중 1 비트의 수를 카운트

 

4. 코드

(풀이1)

class Solution {
    public int solution(int n) {
        int answer = 0;

        String a_str = ""; String one = "1"; String zero = "0";
        String n_str = Integer.toBinaryString(n);
        int size = n_str.length();
        int count = (n_str.replace("0", "")).length();
        int lastOne = n_str.lastIndexOf("1"); int lastZero = n_str.lastIndexOf("0"); 
        while(lastOne < lastZero){
            lastZero = n_str.substring(0, lastZero).lastIndexOf("0");
        }
        if(lastZero == -1)  a_str = "1" + zero.repeat(size-count+1) + one.repeat(count-1);
        else if(lastOne > lastZero){
            a_str = n_str.substring(0, lastZero)+ "1" + zero.repeat(size-lastOne) + one.repeat(lastOne-lastZero-1);
        }
        answer = Integer.parseInt(a_str, 2);*/
        return answer;
    }
}

(풀이2)

class Solution {
    public int solution(int n) {
        int answer = 0;
        //int count = Integer.bitCount(n);
        int count = calcBit(n);
        while(true){
            n++;
            //if(Integer.bitCount(n) == count)    break;
            if(calcBit(n) == count) break;
        }
        answer = n;
        return answer;
    }
    
    int calcBit(int n){
        String s = Integer.toBinaryString(n);
        return (s.replace("0", "")).length();
    }
}