프로그래머스 - 124 나라의 숫자 [C++]

 이 문제는 진법 변환 문제이다. 나는 처음에 이 문제를 백트래킹을 이용해서 풀었으나, 효율성 검사에서 시간 초과가 나왔다. 아무리 최적화를 해도 시간 초과가 나온다. 그래서 검색을 해보니 단순 진법 문제였다. 이 문제에서 핵심은 3으로 나눈 나머지가 0일 때 4를 추가해주고, n을 1 빼줘야 값이 제대로 나온다는 것이다. 그 점만 파악하면 쉽게 풀 수 있었을 것 같다.

 

 

#include <string>
#include <vector>
#include <cmath>

using namespace std;

string solution(int n) {
    string answer = "";
    
    while (n > 0) {
        int rem = n % 3;
        n /= 3;
        
        if (rem == 0) {
            answer = '4' + answer;
            n--;
        }
        else if (rem == 1) {
            answer = '1' + answer;
        }
        else if (rem == 2) {
            answer = '2' + answer;
        }
    }
    
    
    return answer;
}