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

문제

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

풀이

• 처음 풀이 (❌)

  1, 2, 4
  11, 12, 14
  21, 22, 24
  41, 42, 44
  이 순서로 진행되므로 벡터에 1에 1, 2, 4 붙여서 넣고, 2에 1, 2, 4 붙여서 넣는 방식으로 문자열 삽입을 이용했다.
  => n 범위가 너무 커서 시간초과 발생

#include <string>
#include <vector>

using namespace std;

string solution(int n) {
    string answer = "";
    string arr[3] = {"1", "2", "4"};
    vector<string> v;
    
    v.push_back("1");
    v.push_back("2");
    v.push_back("4");
    
    for(int i=0; i<n; i++) {
        for(int j=0; j<3; j++) {
            if(v.size() >= n)   break;
            
            string str = v[i];
            str.insert(str.length(), arr[j]);
            v.push_back(str);
        }
    }
    
    answer = v[n-1];
    
    return answer;
}

• 나중 풀이 (🔵)

  3진법으로 생각해서 진법 변환 이용!
  단, 기존의 3진법은 0, 1, 2를 사용하지만, 124 나라에서는 0 대신 4를 이용하므로 계산 과정에서
  나머지가 0인 경우 ➡️몫을 -1하고, 나머지를 4로 바꾸면 됨

코드

#include <string>
#include <vector>

using namespace std;

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