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

 

 

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

코딩테스트 연습 - 124 나라의 숫자 | 프로그래머스

 

오늘은 카카오 코딩 테스트가 아니라 일반 연습 문제를 소개하겠습니다.

어려운 문제에 속하는 사전순으로  k번째 단어나 숫자를 찾는 문제 입니다.

 

하지만 이 문제는 난이도를 많이 낮춘 문제입니다.

 

이 문제에서는 사전순으로 찾는 일반적인 방법을 배우면 되겠습니다.

그리고 제가 짠 지저분한 코드와 다른 분이 짠 깔끔한 코드를 비교해보겠습니다.

 

 

 

1. 사전순 k번째 찾기 일반적인 방법

 

만약 사전순 500,000,000 번째 단어나 숫자를 구하라고 했을 경우, 하나씩 찾다보면 시간초과가 발생할 수밖에 없습니다.

이를 위해서는 크게 점프를 해가면서 빠르게 원하는 값에 다가가야 합니다!

 

크게 점프한다는 뜻은 무엇일까요?

예를 한 번 들어보겠습니다.

 

이진수로 15번째 값을 구해보겠습니다.

우선 설명에 이해가지 않는 부분이 있더라도 그냥 따라가보세요!

 

15번째 이진수는 4자리 숫자로 표현이 가능합니다. 앞자리부터 채워가면서 답을 찾아 가보겠습니다.

 

현재 상태는 1xxx 입니다.

3자리 이진수로 총 8개의 숫자를 만들 수 있습니다. 15에서 8을 뺍니다.

7이 되고, 4자리 이진수에서 7번째 값을 구해봅니다.

 

세번째 자리에 0일 경우(10xx) 만들 수 있는 모든 숫자 갯수는 2^2 = 4 개 입니다. 

7 > 4 이므로, 세번째 자리에는 1이 들어가야 할 것 같네요.

왜냐면, 세번째 자리가 0으로 만들 수 있는 숫자가 1000, 1001, 1010, 1011 이 있는데

7번째는 이를 넘어가기 때문입니다.

7에서 4만큼을 점프했으므로 빼줍니다. 7 - 4 = 3 입니다. 

이제는 11xx에서 3번째 값을 구하면 되네요.

 

현재 상태는 11xx 입니다.

두번재 숫자가 0일 경우 위에서 설명한 것과 마찬가지로 하면, 3 > 2 이므로 두번째 숫자는 1 이겠군요.

3 - 2 = 1 이 되겠고, 이제 111x에서 1 번째 숫자를 찾아보겠습니다.

 

현재 상태는 111x 입니다.

여기서 1번째 숫자는 1110 이 되겠습니다!

답은 '1110' 입니다.

 

 

 

이런 방식으로 찾아갑니다. 아래 두 문제도 쉽지 않겠지만, 이런식으로 풀어가면 됩니다.

 

https://www.acmicpc.net/problem/2201

2201번: 이친수 찾기

https://www.acmicpc.net/problem/1256

1256번: 사전

 

 

 

 

 

 

이제 이 문제를 풀어봅시다!

이 문제는 아주 단순합니다. 3진법을 구하는 문제와 전혀 다를 것이 없습니다.

하지만 저는 너무 어렵게 생각해서 아주 오래걸리고, 코드도 지저분합니다. ㅠㅠ

 

1, 2, 4

11, 12, 14

21, 22, 24

41, 42, 44

 

규칙을 찾아보면 첫번째 자리숫자나 두번째 자리숫자나 1, 2, 4가 단순 반복합니다.

첫번째 자리 숫자는 3으로 나눈 나머지 값이 0일 때 1, 1일 때 2, 2일 때 4 가 됩니다.

 

좀 더 수학적으로 표현하여, 4214 는 몇번째 숫자일지 생각해 봅시다.

3 * 3^3 + 2 * 3^2 + 1 * 3^1 + 3 * 3^0 = 81 + 18 + 3 + 3 = 105 번째 숫자 입니다.

 

이런 식으로 생각하면 풀기가 아주 쉬워집니다.

하지만 제 코드는 맨 위에서 설명했던 것과 비슷한 방업으로 풉니다.

 

 

#include<vector>
#include<string>
#include<math.h>
 
using namespace std;
 
string solution(int n) {
    ll digit = 1;           // 몇 자리 숫자인지 기록하는 변수
    
    while(1){               // 몇 자리 숫자인지 계산하는 루프
        ll tmp = (pow(3, digit + 1) - 3) / 2;   // 직접 계산을 통해 구한 식을 사용
        if(n <= tmp) break;
        digit += 1;
    }
 
    n -= (pow(3, digit) - 3) / 2;   // 만약 4자리 숫자라면 3자리 숫자로 만들 수 있는 갯수를 제외 시켜준다
    string ans = "";        
    ll combination = pow(3, digit - 1);     // 각 자리에 하나의 숫자를 배정했을 때, 만들 수 있는 총 조합 갯수
                                            // 예를 들어 xxxx 네 자리 숫자라고 할 경우 맨 앞에 '1'을 놓았을 때
                                            // 1xxx 인 숫자를 총 3^3 개를 만들 수 있다는 뜻 
    int idx = 0;                    // 아래 arr의 인덱스 역할을 하는 변수
    char arr[] = {'1','2','4'};
    
    while(1) {                      // 위에서 설명했던 알고리즘과 같다
                                    // 특이한 점이 있다면, n - combination == 0 일 경우 빼주지 않는다는 것이다
                                    // 만약 6번째 값을 구한다고 가정해보자
                                    // xx 두 자리 숫자이고, 1x / 2x / 4x 중에 하나의 형태를 가질 것이다
                                    // 1x 는 3가지를 만들 수 있고, 6 - 3 = 3 으로 넘어가고
                                    // 2x 는 3가지를 만들 수 있고, 3 - 3 = 0 으로 0이 된다.
                                    // 이렇게 되면 0이 되므로 2x에서 끝나버리므로 0이 될 경우 빼주지 않게 한다
                                    // 아래 알고리즘으로 하게 되면
                                    // 2x이고, 3일 경우, 21, 22, 24 이런 식으로 첫번째 자리 숫자까지 찾아주게 된다. 
        if(n - combination > 0) {
            n -= combination;
            idx += 1;
        }
        else if(n == 1 && combination == 1) {   // 이부분이 좀 특이하다. 모든 숫자를 다 찾았을 때 끝내주어야 하는데 
                                                // 이 조건을 넣어주지 않으면 무한 루프를 돌게 된다
            ans += arr[idx];
            break;
        }
        else {
            ans += arr[idx];
            combination /= 3;
            idx = 0;
        }
    }
 
    return ans;
}

 

 

 

이제는 깔끔한 코드를 볼까요? 

재귀 함수로 작성되어 있어서, 더욱 깔끔합니다.

물론 이론적으로는 단순 루프로 푸는 것이 속도면에서 훨씬 우월합니다.

하지만 제 생각은 재귀함수는 논리적으로 매우 아름답고, 코딩량도 적어지는 장점이 있어서 선호하는 편입니다.

 

 

 

 

#include<vector>
#include<string>
 
using namespace std;
 
string solution(int n) {
    if (!n) return "";        // 0으로 떨어졌을 경우 더이상 탐색할 필요가 없으므로 리턴한다.
 
    int t = n/3, rem = n % 3;    // 십진수를 이진수로 바꾸는 알고리즘을 떠올려보면 이해하기 쉽다
 
    if (!t) return to_string(rem);    
    else if (!rem) return solution(t - 1) + "4";
    
    return solution(t) + to_string(rem);
}