[프로그래머스] 124 나라의 숫자 (재귀법)

이 글에서는 프로그래머스 - 124 나라의 숫자 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

재귀법 좋아하시는 분 계세요? 재귀법하면 제일 먼저 떠오르는게 피보나치 수열인데 드디어 그 틀을 좀 벗어날 수 있을 것 같습니다.

문제를 풀고 다른 분들 풀이 보니까 진법의 원리를 이용해서 푸신 분들이 많던데 저도 처음 풀었을 때 나온 풀이가 3진법이니 가장 직관적인 것이 아닐까 싶습니다. 그러나 3진법 풀이는 이미 다른 블로그에도 많으니 재귀법으로 설명드리겠습니다.

---

풀이 1 : 재귀법

제가 이 포스트를 위해 공을 좀 들였습니다. 예시를 통해 설명을 하는 것이 편할 것 같아 제가 생각하며 풀었던 예시로 가져왔습니다.

우리 세계에서는  n = 47 이라고 표현되는 숫자를 124나라의 숫자 체계로 변환을 하려고 합니다.

결론 부터 말하면 47 = 1142가 되는데 어떻게 나오는지 살펴보도록 하겠습니다.

 

살펴보기 전 2가지 그림을 그려 놓았다고 가정합시다.

1. 우리 세계 정수들이 들어가 있는 [N X 3] 배열

2. num[3] 이라는 전역 변수에 들어가 있는 1, 2, 4

 

47은 15번째 줄 2번 째 열에 있죠, 그러니 (15, 1) 라고 나타낼 수 있습니다. (row = 15, col = 1 → num[col] = 2)

그렇다면 row 였던 15의 위치는 어딘가요? (4, 2) 입니다. (row = 4, col = 2 → num[col] = 4)

그렇다면 15의 row인 4의 위치는 어디죠? (1, 0) 입니다. (row = 1, col = 0 → num[col] = 1)

마지막으로 4의 row인 1의 위치는 (0, 1)로 나타낼 수 있습니다. (row = 0, col = 1 → num[col] = 2)

이렇게 한 숫자가 위치해 있는 row와 col을 구하여 row는 재귀적으로 그 다음 숫자를 탐색할 용도로 쓰고,

col은 현 단계에서 찾을 수 있는 끝 숫자를 num 배열에서 찾는 용도로 사용하면 됩니다.

정답용이 아닌 직접 살펴보고 싶으신 분들은 아래 더 보기를 누르셔서 복사해 쓰시면 됩니다. (답은 함수만 복사하시면 됩니다)

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

using namespace std;

int num[3] = {1, 2, 4};

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

    int row, col;
    row = (n - 1) / 3;
    col = (n - 1) % 3;
    if(row == 0){
        return to_string(num[col]);
    } else{
        cout << "[ " << row << ", " << col << " ]" << endl;
        return solution(row) + to_string(num[col]);
    }

    return answer;
}

int main(void){
    int n = 47;
    cout << "answer: " << solution(n) << endl;
}

#8 : 1, 2, 4를 배열 num에 전역변수로 선언해서 끝 숫자를 찾을 때 이용

#14 ~ 16 : row는 몫으로 col은 나머지로 구할 수 있으나 숫자가 0부터 시작하는 것이 아니라 1부터 시작해서 n - 1을 하고 계산해야 한다. 만약 0, 1, 2, 3, 4, 5에 해당하는 124 숫자 체계가 1, 2, 4, 11, 12 였다며 n / 3 또는 n % 3을 해도 되지만 1부터 시작하기 때문에 n - 1을 해야 한다.

#17 ~ 19 : 어떤 숫자의 row가 0이라면 더 이상 재귀를 통해 row, col을 구할 수 없으므로 재귀의 종료 조건이 row == 0에 해당한다.

#19 ~ 22 : 어떤 숫자의 row가 0이 아니라면 계속해서 재귀를 해야하므로 row에 대한 재귀를 계속하고 col에 해당되는 num을 찾아 answer의 끝에 붙인다.(answer가 string이라 끝에 붙인다라고 표현했습니다.)