[프로그래머스 / Level_2 / C++] 다음 큰 숫자

단순 계산 문제이다. 

 

#접근방법 

 

자료구조, 알고리즘 그런거 쓰인거 없이 문제 조건을 보고 무작정쳐서 푼 문제이다. 

이 방식보다 더 효율적인 방법인 분명히 있을 거라고 보지만 0.01ms 로 모든 테스트 케이스를 통과하였으니, 

더 나은 방식을 찾아보는 것은 생략한다. 

 

먼저, n값을 받으면 이진수로 변환하여 문자열에 저장한다. 

이 로직에서는 이진수가 반대로 뒤집혀진 상태로 저장되어있는 것을 기억하자. 

 

해당 이진수 문자열에서 1의 개수가 같은 상태를 유지하면서 큰 값을 구해야한다. 

그렇기 때문에 가장 가까운 1의 위치를 찾고 그 위치로부터 인접한 모든 1을 0으로 바꿔주고 

최초 0을 만난 경우 그 위치를 1로 바꿔준다. 

 

이때, 1을 0으로 바꿔준 개수를 세어주며 이후 반복문이 종료되면 해당 개수의 -1 만큼 

문자열의 인덱스 0부터 차례대로 1로 바꿔준다. 

 

즉, 2진수(역방향) 00111001 이런식이면 

먼저 00000101 로 바꿔주고 그 다음에 11000101로 1을 추가해준다. 

 

이후 해당 이진수 문자열을 10진수로 변화해준다. 

 

*이진수로 변환 후 반복문 종료되면 마지막에 '0'을 추가로 붙여준다. 

 -> why? 이후 1로의 변환작업이 필요한데 문자열의 길이를 초과한 상태로 1이 추가될 수 있기 때문. 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solution(int n) {
    int answer = 0;
    string s=""; 
    while(n){
        s+=n%2+'0'; 
        n/=2;
    }
    s+='0'; 
    int pos = s.find('1'); 
    int cnt_1 =-1; 
    for(int i=pos; i<s.size(); i++){
        if(s[i]=='1'){
            s[i]='0'; 
            cnt_1++; 
        }
        else {
            s[i]='1'; 
            break; 
        }
    }
    pos=0; 
    while(cnt_1--){
        s[pos++]='1'; 
    }
    int mul=1; 
    for(int i=0; i<s.size(); i++){
        if(s[i]=='1'){
            answer+=mul; 
        }
        mul*=2; 
    }

    return answer;
}

코딩테스트 연습 - 다음 큰 숫자