Algorithm - 124 나라의 숫자

프로그래머스 코딩테스트 연습 Level 2 Python

내 답안

def solution(n):
    answer = []
    while True:
        a = list(divmod(n, 3))
        if a[1] == 1:
            answer.append("1")
            if a[0] == 0:
                return "".join(reversed(answer))
        elif a[1] == 2:
            answer.append("2")
            if a[0] == 0:
                return "".join(reversed(answer))
        elif a[1] == 0:   
            answer.append("4")
            if a[0] == 0 or a[0] == 1:
                return "".join(reversed(answer))
            else:
                a[0] -= 1
        n = a[0]

풀이과정

3개의 숫자만으로 이루어진 124 나라의 숫자로 표현하기 위해서는 몫과 나머지가 필요하다고 판단했다. 때문에 divmod 함수를 사용해서 몫과 나머지를 a에 담았다. 그러나 124 나라의 숫자의 1의 자리는 나머지에 따라 추가해주면 됐지만 몫이 0보다 큰 경우는 쉽게 찾아내지 못했다.

그러다 어떤 규칙이 있을지 숫자들을 하나씩 124 나라의 숫자로 표현해 보았다.

10진법	124나라	몫	나머지
1	1	0	1
2	2	0	2
3	4	1	0
4	11	1	1
5	12	1	2
6	14	2	0
7	21	2	1
8	22	2	2
9	24	3	0
10	41	3	1
11	42	3	2
12	44	4	0
13	111	4	1
14	112	4	2
15	114	5	0
16	121	5	1
17	122	5	2
18	124	6	0

위 표를 보면 나머지가 0인 경우를 제외하고 몫이 1인 경우는 1, 2인 경우는 2, 3인 경우는 4, 4인 경우는 11이 붙는 것을 볼 수 있다. 몫이 있는 경우는 몫에 해당하는 10진법 수를 앞에 붙여주면 된다. 숫자가 커지고 자릿수가 커질 수록 그 작업은 반복될 것이다. 때문에 몫을 또다시 3으로 나누고 몫과 나머지에 따라 1,2,4 중에 추가하면 된다. 즉 몫이 0이 될 때까지 3으로 나누는 작업을 반복하면 된다. 때문에 while문 안에 코드를 작성했고 나누어질 n을 몫인 a[0]을 while문 마지막에 추가하여 해당 작업을 반복하게 하고 몫이 0이 되면 return을 통해 값을 반환해 while문이 종료되도록 한다.

하지만 또 하나의 문제점이 존재한다. 나머지가 0인 경우 몫이 0이 아니어도 자릿수가 추가되지 않는다. 즉 나머지가 0인 경우는 몫이 -1된 경우와 동일하게 판단해야한다. 때문에 n = a[0]이라고 하기 전에 나머지가 0일 때 몫이 0이거나 1인 경우는 바로 return을 실행하고 1보다 크다면 a[0] -= 1을 추가한 것이다.

다른 사람의 풀이

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

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

    return answer

똑똑한 사람은 정말 많다.

추가될 문자를 list에 먼저 담고 while문을 돌려서 n을 3으로 나눈 값을 index로 사용하기 위해 1을 빼고 n-1을 3으로 나눈 나머지를 list index로 보내서 answer에 답을 추가한다. 이 때 answer = num[n%3] + answer처럼 answer를 뒤에 더한 이유는 더해지는 숫자가 1의 자리의 위치부터 더해지기 때문에 answer를 뒤에서 더한다.

그 후에 n=n-1을 3으로 나눈 몫을 n에 담아서 같은 작업을 반복한다. n이 0이 되는 순간 즉 몫이 0이 되는 순간 while문은 종료되고 그동안 더해진 answer가 return된다.

다른 사람의 풀이

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

똑똑한 사람은 정말 정말 많다.

어쩌면 위의 코드보다 쉽게 이해될 수도 있다. 재귀함수를 사용해서 while문처럼 같은 작업을 나누어질 대상이 3 이하가 될 때까지 반복하게 한다. 이 때 나머지 값을 문자열의 index를 사용해서 아주 간편하게 표현했다.