프로그래머스 LV.2 다음 큰 숫자

 

https://school.programmers.co.kr/learn/courses/30/lessons/12911

프로그래머스

 

 

 

테스트 케이스는 통과하지만 최적화에 실패한 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

long long binary(int n) {
    stack<int> stk;
    string b_str = "";
    while (n != 0) {
        if (n % 2 == 1) stk.push(1);
        else stk.push(0);

        n /= 2;
    }

    while (!(stk.empty())) {
        b_str += stk.top() + '0';
        stk.pop();
    }

    return stoi(b_str);
}

long long cntOne(int n) {
    string str = to_string(n);
    long long cnt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '1') cnt++;
    }

    return cnt;
}

int solution(int n) {
    long long answer = 0;

    long long b_n = binary(n);
    long long cnt1 = cntOne(b_n);
    answer = n;
    long long cnt2 = 0;
    long long b_nm = 0;
    while (true) {
        if (cnt2 == cnt1) break;

        b_nm = binary(++answer);
        cnt2 = cntOne(b_nm);
    }

    return answer;
}

 

 

 

자료형을 일단 바꾸어 보는 방법으로 접근했다.

 

binary 함수의 return 값을 long long으로 바꾸었으나,

일단 메모리 오류는 고쳐졌으나 실패가 떴다.

 

 

고민하다가 string으로 바꾸어보았다.

string binary(int n) {
    string str;
    while (n > 0) {
        int binary = n % 2;
        n /= 2;
        str = to_string(binary) + str;
    }
    return str;
}

long long cntOne(string const &str) {
    int cnt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '1') cnt++;
    }

    return cnt;
}

int solution(int n) {
    int answer = 0;

    string b_n = binary(n);
    long long cnt1 = cntOne(b_n);
    answer = n;
    long long cnt2 = 0;
    string b_nm = "";
    while (true) {
        if (cnt2 == cnt1) break;

        b_nm = binary(++answer);
        cnt2 = cntOne(b_nm);
    }

    return answer;
}

 

통과했다.