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

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/12899

코딩테스트 연습 - 124 나라의 숫자

 

10진수 입력값을 '124 숫자'로 바꾸어 출력하는 문제입니다.

124 숫자는 모든 값을 '1', '2', '4'를 이용해 나타냅니다.

 

문제에서 주어진 예시를 확장해 보면 아래와 같습니다.

 

10진수	124 숫자	10진수	124 숫자	10진수	124 숫자
1	1	6	14	11	42
2	2	7	21	12	44
3	4	8	22	13	111
4	11	9	24	14	112
5	12	10	41	15	114

접근한 방법

숫자 3개를 이용하여 값을 나타낸다고 하면, 바로 떠오르는 것이 '3진법' 입니다.

2진법이 0, 1 두 개의 숫자를 이용해 모든 값을 표현하듯, 3진법은 0, 1, 2를 이용해 모든 값을 표현합니다.

 

그러면 10진수를 3진법으로 표현해 볼까요?

10진수	3진법	10진수	3진법	10진수	3진법
1	1	6	20	11	102
2	2	7	21	12	110
3	10	8	22	13	111
4	11	9	100	14	112
5	12	10	101	15	120

 

보시는 바와 같이 몇몇 값은 겹치지만, 겹치지 않는 값이 존재합니다.

이번에는 124 숫자와 3진법 값을 비교해 보겠습니다.

 

124 숫자	3진법	124 숫자	3진법	124 숫자	3진법
1	1	14	20	42	102
2	2	21	21	44	110
4	10	22	22	111	111
11	11	24	100	112	112
12	12	41	101	114	120

 

두 경우가 일치하지 않는 경우는 언제일까요?

우선, 각각 사용하지 않는 숫자가 있습니다. 124 숫자는 0, 3진법은 4를 사용하지 않습니다.

 

그렇다고 단순히 숫자를 치환해서는 해결될 문제가 아닙니다.

3진법은 0에서부터 세기 시작합니다. 즉 0, 1, 2의 다음 순서는 10으로, 두 자리 수가 됩니다.

반면 124 숫자는 1에서부터 세기 시작합니다. 3진법의 10에 해당하는 값은 124 숫자에서는 아직 한 자리 수입니다.

 

이것을 감안하여 구현해 주면 됩니다.

기본적인 구현 방법은 n진수 계산법과 유사합니다.

 

코드 링크: GitHub

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string decimal_to_124 (int n) {
    string answer = "";
    
    // 숫자가 3 이상일 동안 반복
    while(n >= 3) {
        int remaining = n % 3;
        
        // 나머지가 0일 경우, 값을 4로 대체하고, n값을 하나 줄임
        if (remaining == 0) {
            answer = '4' + answer;
            n = (n/3) - 1;
        }
        else {
            answer = to_string(remaining) + answer;
            n /= 3;
        }
    }
    answer = to_string(n) + answer;
    
    // 맨 앞에 0이 있을 경우 제거
    if (answer[0] == '0') return answer.substr(1);
    else return answer;
}

string solution(int n) {
    
    string answer = decimal_to_124(n);
    
    return answer;
}

 

이 문제는 정확성 테스트는 물론, 효율성 테스트까지 있기 때문에 시간복잡도를 고려해서 코드를 작성해야 합니다.

입력받는 수 n은 최대 500,000,000의 값을 가지므로, 제가 작성한 코드에서는 최대 18번 while문이 돌게 됩니다.

아마 3진법으로 계산하고 이를 후처리 하는 방식으로 구현하면 시간복잡도에서 걸리지 않을까... 하는 예상을 해 봅니다.