[Level 2] 4. 다음 큰 숫자

4. 다음 큰 숫자

Algorithm - Level 2

- 풀이

1. 이진수로 변환하여 접근하기 위해 string형으로 변환하는 것이 편리

# 방법. 1

2. 연속된 1과 0의 개수가 같다면 뒤에 0을 붙인다.

-> ex) 1100 = 11000

3. 앞 숫자가 0이고 뒤 숫자가 1이면 그 위치를 바꿔준다.

-> ex) 1001 = 1010

4. 3을 만족하면서 현 위치에서 뒤, 뒤에 존재하는 숫자가 1이고 맨 뒤가 0이라면 뒤, 뒤에 숫자를 0으로 바꿔주고 맨 뒤를 1로 바꿔준다.

-> 10110 = 11001

@ stoi(string, index=0, base)

-> string 타입을 int형으로 변환하되, base 진수로 인식하여 변경 

int solution(int n) {
    int count1 = 0;
    int count0 = 0;
    int sf = 1;
    string s = toBinary(n);
    
    for(int i=s.size()-1; i>=0; --i){
        if(s[i]=='1'){
            sf = 0;
            if(++count1==s.size())
                s.insert(s.begin()+1, '0');
        }
        else if(sf==1){
            count0++;
        }
            
        if(i!=s.size()-1 && s[i]=='0' && s[i+1]=='1'){
            s[i] = '1';
            s[i+1] = '0';
            if(s[i+2]=='1' && count0!=0){
                s[i+2] ='0';
                s[s.size()-1] = '1';
            }
            break;
        }
    }
    if(count0 + count1 == s.size())
        s.push_back('0');
 
    return stoi(s, 0, 2);
}

: 테스트 케이스 1을 통과못한다.

-> 어떤 케이스인지 모르겠음.

# 방법.2

2. 현 숫자에서 1씩 증가시켜 2진수로 변경해 1의 개수가 같다면 그 값을 반환한다.

string toBinary(int n){
    string s;
    while(n!=0) {s=(n%2==0?"0" : "1")+s; n/=2;}
    return s;
}
 
int solution(int n){
    string s = toBinary(n);
 
    int count = 0;
    for(auto c:s)
        if(c=='1')
            count++;
    
    while(1){
        n++;
        string tmp = toBinary(n);
        int tmpC=0;
        for(auto c:tmp)
            if(c=='1')
                tmpC++;
        
        if(count==tmpC)
            return n;
    }
}