프로그래머스 level 2 '124 나라의 숫자' C++ 풀이 과정 및 코드

프로그래머스 level02 '124 나라의 숫자' C++ 풀이 과정 및 코드

문제 설명

기존의 10진법으로 표현된 자연수가 주어지면, 1과 2, 4만을 사용한 숫자 체계로 변환하여 string값으로 리턴시키는 문제이다.

주의할 점

1. 1,2,4라는 연속적이지 않은 숫자로 구성된 체계
2. 0부터가 아닌, 자연수만 존재함
3. string값으로 리턴함
4. n의 최대 범위

생각의 흐름

1. 3개의 숫자로 이루어져 있으니 3으로 나눈 몫과 나머지를 사용해야겠다.

   
   

2. n을 3으로 나눈 나머지를 이용해 124로 변환한 숫자의 마지막 자리 값은 구할 수 있었지만, n의 나머지 숫자들을 자릿수마다 하나하나 구하는 방법을 생각해보니, 3의 거듭제곱의 합을 구해야 하는 방법밖에는 생각이 나지 않았다.(자릿수가 늘어나는 기준은 3, 9, 27...으로 3의 거듭제곱 수이고 누적된 숫자로 보면 3, 12, 39..이다. 즉, n이 3보다 크면 2자리 이상의 수이고 n이 12보다 크면 3자리 이상의 수인 셈)
   -> n의 최대범위를 고려할 때 이렇게 푸는 건 불가능 가까운 풀이 방식이기에 폐기

   
   

3. 예제로 주어진 표를 보다가, 124로 변환한 숫자를 나누어서 보기 시작
   -> 재귀함수로 구현하여도 깊이가 깊어지지 않는다고 판단하여 채택 !

알고리즘 설명

예제로 주어진 표

10진법 숫자 6의 변환 결과 14는 크게 앞부분인 1과 마지막 숫자로 나뉜다. 마지막 숫자는 앞서 말했듯이 n인 6을 3으로 나눈 후의 나머지로 구할 수 있다. 변환 결과의 앞부분은 6에서 몇 번 동안 3을 빼야 1, 2, 3 중 하나로 만들 수 있는지에 따라 결정된다. 6에서 3을 1번 빼면 3이 되기 때문에, 6의 앞자리에는 1의 변환값인 1이 들어간다.

세 자리 예시를 들어보겠다. 13의 변환값은 111이다. 13을 3으로 나눈 나머지는 1이기에 변환 결과의 마지막 숫자는 1이고, 13을 4번 빼면 1로 만들 수 있기 때문에 13의 변환값의 앞부분은 4의 변환값인 11이다.

코드

변환값의 앞부분을 구하는 코드는 뺄셈의 반복이므로 나눗셈으로 구현하였다. 1, 2, 3이 한 묶음인데 1과 2를 3으로 나눈 몫은 0인 반면, 3을 3으로 나눈 몫은 1이기 때문에 셋을 3으로 나눈 몫으로 한데 묶을 수가 없어서 n에서 1을 뺀 후 계산하였다.
n에서 1을 뺏기 때문에 마지막 숫자를 구하는 조건도 변화하였고, 앞부분을 구할 때도 1을 빼주었다.

#include <string>
#include <iostream>

using namespace std;

string toNumber124(int n) {
    if (n == 0) return "1";
    if (n == 1) return "2";
    if (n == 2) return "4";

    return toNumber124(n / 3 - 1) + toNumber124(n % 3);
}

string solution(int n) {
    string answer = "";

    answer = toNumber124(n - 1); //몫이 같은 것들끼리 한 묶음으로 만들기 위해

    return answer;
}

디버깅 기록

1. n에서 1을 뺀 후 계산하기 때문에 그 여파로 다른 부분의 조건들도 수정해주어야 했다. 기존에 주어진 값을 살짝이라도 변형하기로 마음먹었다면 책임지고 다른 부분까지 제대로 변형해야 한다. 다시 말하면, 책임만 질 수 있다면 기존에 주어진 값을 변형해 구해도 괜찮다는 뜻!

2. 리턴값이 string이라는 것에서 착안하여 자릿수마다 값을 구해서 뒤에 붙여넣는 식으로 하면 되겠다고 생각했는데, 자릿수마다 나누는 것은 연산이 너무 많아져서 나누는 범위를 마지막 자리와 그 앞부분으로 확장시켰다. 나누는 기준을 현명하게 세우자.