[프로그래머스] 코딩테스트 연습 - 124 나라의 숫자(Python)

문제 설명

문제

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법	124 나라	10진법	124 나라
1	1	6	14
2	2	7	21
3	4	8	22
4	11	9	24
5	12	10	41

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한

• n은 50,000,000이하의 자연수 입니다.

입출력 예시

입출력 예

n	result
1	1
2	2
3	4
4	11

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

프로그래머스

Level2 문제입니다. 구현과 그리디 유형이라고 할 수 있습니다. 원하는 값이 나올 때 까지 반복문을 순회하기 때문인데요, 맨 처음 이 문제를 풀었을 때는 틀렸습니다. 규칙성을 찾을 때에도, 공비수열인 것에만 집중해서 정말 핵심인 규칙성을 놓쳤는데요,

제가 처음 접근했던 규칙은 아래 그림과 같습니다.

124나라에서는 수가 1, 2, 4 로만 이루어져 있습니다. 어떤 수를 1, 2, 4 로 구성된 숫자로 표현 할 때, 결국 n이 몇자리 숫자로 표현되는지 알아내는 것이 관건이라고 생각했습니다.

예를 들어, 15 라는 숫자는 12까지가 2자리로 표현되는 범위니까, 3자리로 표현되는 것을 알 수 있겠고, 그 중에서도 3번째 (13,14,15) 순서에 위치하는 것을 알 수 있습니다.

 

제가 처음 풀었던 로직의 코드는 아래와 같습니다.

import itertools

def solution(n):
    answer = ''
    sets = "124"
    
    if n <= 3:
        if n == 1: answer = 1
        elif n == 2 : answer = 2
        else: answer = 4
    
    elif n > 3:
        exponent = 0
        tmp = 0
        for i in range(1,n):
            tmp += 3 ** i
            if tmp > n :
                tmp -= 3** i
                exponent = i
                break

        tmp_mod = n - tmp
        data = itertools.product(sets, repeat = exponent)
    
        for idx,x in enumerate(data):
            if idx == tmp_mod -1:	# 인덱싱은 0부터이므로 tmp_mod-1을 해줌
                answer = ''.join(x)
                break

    return str(answer)

먼저, [1,2,4] 의 세 숫자로 수를 표현해야 하는데, 몇자리 숫자인지 알아내야 하므로 중복조합이 필요하다고 생각했습니다.

예를 들어 [1,2,4] 로 만들 수 있는 모든 2자리 숫자라 하면, [11,12,14,21,22,24,41,42,44] 처럼 중복해서 모두 뽑아내야 하기 때문입니다. itertools를 import한 이유입니다.

 

n 이 3보다 큰 경우에, 1부터 n까지 돌면서, n 직전까지 완전히 표현가능한 자리수는 몇자리인지 찾아내는 로직을 구현했습니다. tmp 라는 변수에 3을 곱해가면서 n을 초과하는지를 판별하고 초과한다면, tmp에서 직전에 더해줬던 3의배수값을 다시 빼주고 탈출합니다. 이 때, n 전까지는 완전히 i자리 까지 표현가능하다는 뜻이므로, exponent 변수에 i를 저장해줍니다.

이해가 안가실 수 있으니, 예를 들어서 설명드리겠습니다.

n이 20이라고 가정해본다면, 20까지 공비가 3인 배열을 차례로 더합니다. 즉, 3 + 9 + 27 + ... 처럼 숫자를 더하다가, 그 합이 20을 넘어간 경우는 27을 더해줬을 때입니다. 3+9(=12)로 20 안으로 범위가 들어오는데, 27을 더해줌으로써 20을 초과한 것입니다. 그럼 20 전 까지는 완전히 2자리 숫자는 표현 가능(4부터 12까지는 완전히 2자리 숫자로 표현 가능)한 숫자가 존재하고, 20은 세 자리 숫자로 표현되는 수인 것을 알 수 있습니다.

 

다른 예를 살펴볼까요? n이 11라고 가정해본다면, 3 + 9 를 할 때, 11을 초과해버립니다. 그러면, 11 범위 안에 완전히 1자리 숫자로 표현 가능한 수가 존재하는것이고, 11은 2자리 숫자로 표현된 수라는 것을 알 수 있습니다.

 

그럼 그 숫자가 몇자리로 표현되는 것을 알았다면, 중복조합 중에서 몇번째 순서인지도 알 필요가 있습니다. 

앞의 예를 가져온다면, 20은 세 자리로 표현된 숫자인데, [1,2,4] 로 표현할 수 있는 모든 세 자리 숫자 리스트인 [111,112,114,121,122,124,141,142,144,...,442,444] 중에서 8번째인 것을 알 수 있습니다.

 

그래서, 나머지 계산을 해야 합니다. n에서 앞서 계산했던 tmp를 빼줘야 하는데요, tmp는 n보다 자리 수가 1개 적은 수 입니다. 즉, n을 k자리 숫자로 표현된 수라면, tmp는 k-1자리 숫자로 표현된 수 중에서 가장 최대의 값을 뜻합니다.

정리하자면, k자리 숫자로 표현되는 수인 n이 k자리 숫자로 표현된 모든 수 중에서 몇 번 째 수 인지 알려면, k-1자리 숫자로 표현된 최대의 수를 n에서 빼면 몇번 째인지 알 수 있는 것입니다.

 

data라는 튜플 리스트를 만드는데, "124"를 이용해서 exponent 만큼 중복 조합을 뽑아냅니다.

그 중에서 (n-tmp) -1 번째인 숫자가 바로 n이 124나라에서 표현되는 수인 것입니다. 

튜플리스트이므로, 이것을 스트링으로 변환하는 join을 해주면, 답이 됩니다.

 

간단한 문제인데, 설명이 너무 장황했네요. 하지만, 이것은 결국 틀렸습니다.

물론, 정확성 테스틑 모두 맞았지만, 효율성에서 모두 시간초과가 나버렸기 때문인데요, 효율성을 잡으려면, tmp를 구하는 for문을 다시 점검할 필요가 있다고 생각했습니다. for문에서 하나씩 3의배수를 더해가면서 찾는 것은 그 만큼 시간이 불필요하게 소비될 수 있기 때문입니다. 혹은, 중복조합 리스트를 만드는데에 시간이 오래 걸리는 것일 수도 있겠구요. 전자의 경우, 코드를 고쳐봤는데, 큰 차이가 없는 것 같았습니다. 

아무래도, 문제는 product를 이용한 중복조합 쪽에서 시간 비효율이 발생한 것 같았어요.

 

몇 자리 숫자인지 바뀌는 수는 아래와 같습니다.

[1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244]

만약, n은 50,000,000이하의 자연수 입니다.

5천만 전까지는 16자리로 나타내는 수일 텐데, 순열조합은 너무나도 많겠죠.

 

순열 조합 itertools를 사용하기 보다는 조금 더 획기적인 아이디어를 생각해볼 필요가 있었습니다.

구글링을 통해 풀이를 살펴보니, 3진법을 고려해서 푸는 방법이 있었습니다.

 

먼저, 3진법을 고려한 풀이를 살펴보겠습니다.

•  n이 3의 배수가 아니라면, 3진법을 구하는 것과 동일하게 3으로 나눈 나머지를 저장하고, n을 3으로 나눈 몫으로 저장합니다.
• n이 3의 배수라면, 무조건 '4'를 추가하고, n을 3으로 나눈 몫에서 1을 뺀 값을 저장합니다. (3진법에 0이 포함되지 않기 때문에)

아래 그림을 살펴봅시다

규칙이 보이시나요?

코드로 나타내면, 비교적 짧은 코드로 나타낼 수 있습니다.

def solution(n):
    answer = ''
    while n:
        if n % 3 != 0:  # 3의 배수가 아니라면,
            answer += str(n % 3)
            n //= 3 
        else:   # 3의 배수라면,
            answer += "4"
            n = n//3 - 1
    return answer[::-1]

조금은, 허탈할 수도 있습니다. 왜이렇게 간단하게 풀릴까..level2 인 이유가 있는 셈이겠죠. 저도 조금 허무했습니다만, 로직은 정말 간단한 건 사실입니다.

n이 0이 될 때 까지 계속해서 순회합니다.

n이 3의 배수가 아니라면, n을 3으로 나눈 나머지를 answer에 더해주고, n은 몫으로 갱신합니다.

n이 3의 배수라면, 124 나라에는 0이 없으니까 n을 3으로 나눈 나머지인 '0'을 '4'로만 바꿔주고, answer에 더합니다. 그리고, n은 (몫-1)로 갱신합니다.

 

최종적으로 나온 answer를 거꾸로 뒤집어주면, 답이 되는 것입니다. 뒤에서부터 추가가 되는 로직이니까요.

이렇게 해주니, 효율성도 빠르게 통과되었습니다.

다른 사람들의 풀이 중에서 획기적으로 짧은 코드도 존재했습니다.

def solution(n):
    if n <= 3:
        return '124'[n-1]
    elif n > 3:
        q,r = divmod(n-1,3)
        return solution(q) + '124'[r]

n이 3이하라면, 1,2,4 를 순서대로 반환해주고,

n이 3초과인 숫자라면, (n-1)을 3으로 나눈 몫과 나머지를 q와 r에 각각 저장합니다.

이 때, n-1을 해주는 이유는 3진법에 0이 포함되지 않기 때문입니다. divmod(n,3)이 아닌 divmod(n-1,3)을 해줍니다.

※ divmod(a,b)
=> a를 b로 나누었을 때 몫과 나머지를 tuple의 형태로 return

divmod(10,3)  # (3,1)
divmod(12,3)  # (4,0)​

간단하지만, 효율성 문제를 해결해야하는 난관 때문에 조금은 애를 먹었던 문제였습니다. 직관적인 구현도 좋지만, 더 높은 효율성을 생각해내는 코드를 짤 수 있어야겠습니다.