[프로그래머스] 123 나라의 숫자_Python level2

🔒 문제

https://school.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이하의 자연수 입니다.

입출력 예

n	result
1	1
2	2
3	4
4	11

---

🔓 풀이

🔑 문제 해결 / 코드

def trinary_digit(a):
    rev_base = ""
    base = ["4", "1", "2"]
    while a > 0:
        a, remainder = divmod(a, 3)
        if remainder == 0:
            a = a - 1
        rev_base += base[remainder]
    return rev_base[::-1]

def solution(n):
    return trinary_digit(n)

---

🍀 Story

처음 이 문제를 봤을 때는 '어 이거 3진법 만드는 방법으로 쉽게 풀 수 있겠네? '라는 생각이 들었다. 

그리고 3진법 로직을 구현 했는데 막상 실행을 하니 문제가 발생했다. 

내용만 보면 3진법인것 같은데 왜 안될까?

# 10진수 3진수로 변환
def trinary_digit(a):
    rev_base = ""
    while a > 0:
        a, remainder = divmod(a, 3)
        rev_base += str(remainder)
    return rev_base[::-1]

 

1. n의 범위

일단 3진법은 0부터 시작이 되어 0, 1, 2 3가지 수로 숫자 데이터를 표기한다.

문제에서는 자연수만 취급을 하기에 0이 없음으로 일반적인 3진법과 달라지게 된다.

 

2. 00 == 0

지금 124나라와 3진법을 매핑항다면 (0: 1), (1: 2), (2: 4)로 매핑된다. 

여기서 문제가 발생하는데 사실 3진법에서 0이 사용되긴 하지만 0이 앞자리로 나오는 수는 10진법 0을 3진법 0으로 표기하는 게 유일하다.

다시 말하면 00이든 000이든 결국 0이며 3진법에서 두자리가 되는 첫 번째 수인 3(10진법)은 00으로 표기되지 않고 10(3진법)으로 표기된다.

124 나라에서 처음 두자리가 되는 첫 번째 수인 4(10진법)를 124 나라 기법으로 표기하면 11이 되는 것과 다르게 차이점이 생기게 된다.

 

3진법으로 해결은 되지 않았지만 비슷한 규칙성을 찾을 수 있을 거라 생각해서 다시 패드를 꺼냈다.

규칙성이 보이는가..?

3가지 규칙성을 찾을 수 있었는데 파랑, 빨강, 노랑으로 구분선으로 구분 지었다.

 

1. 노란색 규칙 + 파란색 규칙 : 나머지가 0, 1, 2일 때 끝자리가 4, 1, 2 가 되는 규칙

이 규칙을 만족하기 위해 나머지를 인덱스로 판단해서 기존의 base = ["1", "2", "4"]의 원소 순서를 base = ["4", "1", "2"]로 변경하였다. 

 

2. 빨간색 규칙 + 파란색 규칙 : 앞의 규칙을 따라가면 나머지가 0이 되는 경우는 앞자리가 제대로 매칭이 되지 않는다. 그 이유는 빨간색 규칙이 파란색 규칙과 일치하지 않기 때문인데 이 부분을 일치시켜주기 위해서 나머지가 0일 때는 몫에서 1을 빼서 규칙을 동일하게 만들어줬다.

세가지 규칙을 모두 동일하게!!

코드로는 if remainder == 0: a = a - 1 부분을 추가해서 문제 풀이를 완료했다.