[프로그래머스] 124 나라의 숫자 풀이

1. 문제

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

2. 풀이 방법

처음에 이 문제를 풀었을 때 헷갈렸던 점은 3진법을 그대로 숫자만 변형하면 된다고 생각했던 것입니다. 하지만, 실제로는 3진법의 풀이와 매우 다릅니다.
- 9은 3진법으로 100이지만, 124 나라에서는 24입니다.
각 자리 숫자는 3개, 9개, 3^3개 와 같은 3의 n제곱 개수 만큼 가지고 있습니다.
3의 제곱수(0, 3, 9 ….) 만큼 for문을 수행합니다.
- 1의 자리부터 시작하여 3의 나머지 연산을 통하여 0, 1, 2 중 하나의 값을 얻어냅니다. 해당 수는 n자리의 자리 수가 됩니다.
- n을 3으로 나눈 후에 다음 단계를 수행합니다.

3. 소스코드

3.1. pow를 사용한 효율성 테스트 실패 코드

O() 수준의 복잡도가 아니라 약간의 시간 상승에도 채점에 제한을 거는 것 같습니다. 아래의 코드는 pow를 사용하여 통과할 수 없었습니다.

#include <string>
#include <vector>
#include <algorithm>    //reverse
#include <cmath>
using namespace std;
string solution(int n) { 
    string num_3 = ""; 
    string answer = "";
    int div_num = n;
    for(int i = 1; i <= 19 ; i++){
        if(div_num <= 0) break; 
        char add_char;
        int sub = ((div_num - 1) / (int)pow(3, i-1)) % 3;
        switch(sub){
            case 0:
                add_char = '1';
                break;
            case 1:
                add_char = '2';
                break;
            case 2:
                add_char = '4';
                break;                
        }
        num_3.push_back( add_char );
        div_num -= (int)pow(3, i);
    }
    int str_len = num_3.length();
    for(int i = 0; i < str_len; i++ )
        answer.push_back(num_3[str_len - i - 1]);
    return answer;
}

3.2. pow 대신 곱하기를 이용한 효율성 테스트 통과 코드

#include <string> 
#include <algorithm>    //reverse
#include <iostream> 
using namespace std;
string solution(int n) { 
    string num_3 = ""; 
    string answer = "";
    long long sub_n = n;
    long long div_num = 1;
    for(int i = 1; i <= 19 ; i++){
        if(sub_n <= 0) break; 
        char add_char;
        long long sub = ((sub_n - 1) / div_num) % 3;
        div_num *= 3;
        switch(sub){
            case 0:
                add_char = '1';
                break;
            case 1:
                add_char = '2';
                break;
            case 2:
                add_char = '4';
                break;                
        }
        num_3.push_back( add_char );
        sub_n -= div_num;
    }
    int str_len = num_3.length();
    for(int i = 0; i < str_len; i++ )
        answer.push_back(num_3[str_len - i - 1]);
    return answer;
}

3.3. 위의 풀이를 간결하게 줄인 풀이

#include <string>
using namespace std;
int convert[3] = {1,2,4};
string solution(int n) {
    string str = "";
    while(true){
        n -= 1;
        int tmp = n % 3;
        str = to_string(convert[tmp]) + str;
        n /= 3;
        if(n <= 0) break;
    }
    return str;
}

PREVIOUS[프로그래머스] 주식가격 풀이

NEXT[프로그래머스] 가장 큰 수 풀이