프로그래머스 | N 보다 큰 수

08/25-9/1

<문제>

 

1차 시도)

우선 되는대로 한번 풀어보자

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

int solution(int n) {
    string num = "";
    int one=-1, zero =0;
    
    while(n>=1){
        n%2==1? one++:zero++;
        num = to_string(n%2) + num;
        n/=2;
    } // 이진수 변환
    
    cout << num <<  "\n"; // 점검용 출력
    
    // 0 없으면 맨 앞에 0하나 추가
    if(zero==0) num = '0' + num;
    
    // 1) 제일 앞에 있는 0 바로 그 뒤의 1이랑 자리 바꾸고 거기까지만 저장
    for(int i = 0; i<num.size()-1; ++i){
        num[i]=='1'? one--:zero--;
        if(num[i]=='0' && num[i+1]=='1'){
            num = num.substr(0,i) + "10";
            break;
        }
    }
    cout << num <<  "\n"; // 점검용 출력
    cout << zero  << " " << one <<  "\n"; // 점검용 출력
    
    // 2) 만들어진 수에 남은 0은 전부 앞으로, 남은 1은 전부 뒤로 해서 num에 붙이기
    while(zero > 0 || one >0){
        if(zero > 0){
            zero--; num += '0';
        }
        else {one--; num += '1';}
    }
    cout << num <<  "\n"; // 점검용 출력
    
    // 3) 이진수로 변환
    int ans =0; int bn =1; 
    for(int i = num.size()-1; i>=0; --i){
        if(num[i]=='1') ans += bn;
        bn*=2;
    }
    
    return ans;
}

 

응 어림도 없지 당연히 틀리죠?

 

예외케이스들을 찾아서 수정해보자

2차, 3차 시도)

예외 찾아내서 수정하기

예외부분 1차 수정

// 예외케이스 추가
    if(zero==0) num = '0' + num; // 0 없이 1만 있는 경우
    if(zero==1 && num[num.size()-1] == '0') {num = '0' + num; zero++;} //0이 맨 마지막에만 나오는 경우

 

예외부분 2차 수정

(이번에는 1100000

이런애랑 1000000 이런 식으로

0이 맨 뒤에만 나오는 애들도 처리할 수 있게 수정함.)

 

// 예외케이스 추가***************************
    int ecp =0;
    for(auto x : num) x=='1'? ecp=0:ecp++;
     //0이 없거나 맨 마지막에만 나오는 경우
    if(ecp == zero){
        num = '0' + num;
        if(zero > 0) zero++;
    }

이번에도 실패!

 

ㅇㄴ 이정도면 다시 풀어야될거같은데

아예 접근을 잘못한거같다.

 

저 문제를 찾아보니까 비트변환을 써야된다고 한다

비트변환 공부는 블로그에 다시 정리해야지

 

4차 시도!)

비트변환 적용해서 풀어보기!

#include <bitset>
using namespace std;

int solution(int n) {
    bitset<8>num = n;
    int cnt = num.count();
    
    while(1){
        n++;
        num = n;
        if(num.count() == cnt) return n;
    }
}

비트변환으로 하니까 진짜 간단하게 나온다 대박