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

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12899#

 

문제 설명 : 

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은 500,000,000이하의 자연수 입니다.

문제 풀이 : 

이 문제를 보고 가장 먼저 떠올린 건 3진법이다. 1, 2, 4의 세 숫자만을 이용해서 표현하기도 하고 기본적으로 n진법으로 수를 표현하는 방식과 동일(일의 자리를 하나씩 올리고, 자리 올림 수를 사용)했기 때문이다. 그래도 완전하게 3진법으로 매칭해서 생각하긴 어려웠다. 3진법은 0, 1, 2를 이용해서 수를 표현하는데, 124 나라에는 0이 없기 때문이다. 대신 0이 오는 특성을 파악하면 조금 더 쉽게 생각할 수 있었다. 숫자 0 자체는 자연수가 아니므로 표현 대상이 아니고, 그 외의 0이 사용되는 경우는 10, 20, 30, ... 104 이런식으로 자릿수이기 때문이다. 

3진법	124 나라	3진법	124 나라
1	1	20	14
2	2	21	21
10	4	22	22
11	11	100	24
12	12	101	41

규칙성을 파악해보면 3진법에서 10을 124 나라에서는 4로 표현하고 있다. 

 

따라서 이를 이용해서 만들어 주면 된다. 

from collections import deque

def solution(n):
    answer = deque()
    while n != 0:
        answer.appendleft(n % 3)
        n = n // 3
    while 0 in answer:
        for i in range(len(answer)):
            if answer[i] == 0 and answer[i-1] == 4:
                answer[i-1] = 2
                answer[i] = 4
            elif answer[i] == 0:
                answer[i-1] -= 1
                answer[i] = 4
        while answer[0] == 0:
            answer.popleft()
    answer = ''.join([str(int) for int in answer])
    return str(answer)

그래서 0인 경우를 다 자리 빌림 해서 4로 바꿔주었는데.. 풀면서 코드가 길어지고 명쾌한 느낌이 안 나서 이 방법 말고 다른 방법이 있을 거라는 생각이 강하게 들었다. 위의 내가 푼 풀이로는 예외처리 되어야 할 경우도 많았고, (111 -> 10404 -> 4244 가 되는 경우에는 0을 4로 바꿔주는 작업을 또 해줘야 했다) 뭔가 조금 더 쉽게 설명할 수 있을 것 같은 기분이 들어서였다. (게다가 indent depth가 너무 깊어서 좋은 코드가 아니라고 격하게 느꼈다)

 

문제를 제출하고 나서 다른 분들의 풀이를 보니까, 훨씬 간단한 풀이들을 배울 수 있었다. 풀이 두개를 가져와봤는데, 둘 다 0, 1, 2가 아닌 1, 2, 3을 각각 1, 2, 4에 대응시키는 전략이었다. 사실 문제를 풀어보면서 생각해본 방법이긴 한데, 이 방법엔 집중하지 못했다. 

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

이건 재귀를 이용해서 푼 방법이었다. 재귀는 첫 눈에 보고도 이해가 잘 되는 편은 아니지만 직접 쓰려면 더더욱 헷갈리는데, 재귀를 생각했다는 자체도 신기했고 응용하니 코드가 훨씬 단순해져서 나도 다음엔 적용해보고 싶은 욕심이 생겼다. + divmod를 쓸 생각은 못해서 파이썬 함수들을 제대로 활용하지 못하고 있구나 싶은 마음도 많이 든다. 

 

그리고 개인적으로는 가장 깔끔하다고 생각했던 코드는 다음이었다. 

def change124(n):
    num = ['1','2','4']
    answer = ""


    while n > 0:
        n -= 1
        answer = num[n % 3] + answer
        n //= 3

    return answer

0이 없기 때문에 n에서 1을 빼줬는데, 쉽게 이해되는 코드들이었다. 

 

오늘도 내 코드를 작성하는 것 외에도 먼저 문제를 해결해서 온전히 이해하고 다른 사람의 코드를 보면서 배우는 점이 더 많았던 것 같다.