[프로그래머스 lv2] 다음 큰 숫자 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

n을 이진수로 변환했을 때 1의 개수를 카운트하여, 같은 1의 개수를 갖는 다음 이진수를 리턴하는 문제이다.

n을 이진수로 변환했을 때 1의 개수를 세고, n+1 부터 숫자들을 탐색하며 같은 1의 개수를 갖는 수를 찾는다.

 

주의

백준의 경우 대부분 문제의 시간 제한이 1초라서, 해당 문제를 1초 내에 돌아가는 다른 풀이로 먼저 제출을 했었다.

그런데 TLE이 남...

고수님께도 질문을 해봤으나, 이 문제의 시간복잡도가 너무 타이트하다는 결론을 내렸다.

혹시 자신의 풀이가 1초(연산 횟수 10^8) 내에 들어오는데 자꾸 시간초과가 난다면 너무 자책하지말고 프로그래머스를 약간 탓해보자.(관계자님 보고 계시나요...!)

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int cntOne(int n) {

    int cnt = 0;
    while (n) {
        if (n%2) cnt++;
        n /= 2;
    }
    return cnt;
}

int solution(int n) {

    int cnt = cntOne(n);

    for (int i=n+1; ; i++) {
        if (cntOne(i) == cnt) return i;
    }
    return -1;
}

 

원래 제출했지만 TLE 받은 코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int toDec(const vector<int>& v) {

    int p = 1;
    int n = 0;
    for (int i=v.size()-1; i>=0; i--) {
        n += p*v[i];
        p *= 2;
    }
    return n;
}

int solution(int n) {
    
    int cnt = 0, tmp = n;
    while (tmp) {
        if (tmp%2) cnt++;
        tmp /= 2;
    }
    
    vector<int> v(20);
    for (int i=0; i<cnt; i++) v[i] = 1;
    sort(v.begin(), v.end());

    while (next_permutation(v.begin(), v.end())) {
        int d = toDec(v);
        if (d > n) return d;

    }
    return -1;
}