2023년 11월 14일 알고리즘 문제풀이

문제

124 나라의 숫자

난이도

Lv.2

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(n):
    nums = []
    while n:
        a = n%3
        if a:
            n = n//3
            nums.append(str(a))
        else:
            n = n//3 -1
            nums.append('4')
    nums.reverse()
    answer = ''.join(nums)        
    return answer

코드 자체는 단순해보이지만 해결하는데 정말 어려운 문제였다. 등장할 수 있는 숫자가 3개(1,2,4)였기 때문에 3진법을 이용하면 될 것 같다는 생각 자체는 바로 떠올렸다. 하지만 답을 유추해내기 쉽지 않았는데 추가적인 조건이 있기 때문이다. 아래 표를 통해 설명하겠다.

처음에는 3진법이기 때문에 0,1,2 만 등장할 것이고 이를 각각 1,2,4 로 치환해주면 될 것이라고 생각했다. 하지만 오답이 발생했다.

10진법으로 3일 때 3진법과 124나라의 숫자의 자릿수가 달라진다. 그리고 6일 때는 가장 높은 자리의 숫자가 다르고, 9일때도 가장 높은 자리인 두번째 자리 숫자가 다르다. 10진법 숫자가 3의 배수일 때마다 예외가 발생함을 볼 수 있다. 한 가지 다행인건 그 이후까지 영향을 끼치지 않고 그 이외(3의 배수가 아닐 때)는 그대로 숫자를 치환하면 된다.

3일 때는 숫자 3이 나타날 수 없기 떄문에 자릿수가 올라갔는데 124 나라의 숫자는 0이 없기 때문에 자릿수를 올라갈 필요 없이 첫번째 자리에서 다음 숫자로 설정한 것이다. 따라서 3진법을 기준으로 다음 자리 숫자를 1 깎고, 0이었던 원래 자리 숫자를 4로 설정해주면 된다. 마치 30을 29로 만들어주는 느낌이라고 생각하면 조금 이해가 될 것이다. 6일 때도 2를 1로 깍고 0을 4로 바꾼 것이고 9일 떄도 3을 2로 깍고 0을 4로 바꿔준 것이다.

• Next
  파이썬 알고리즘 : X만큼 간격이 있는 n개의 숫자