[programmers] Level 2 124 나라의 숫자.py

프로그래머스 Level 2 124 나라의 숫자를 파이썬을 통해 풀어보았다. 

 

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

코딩테스트 연습 - 124 나라의 숫자

124 나라의 숫자.py

tomy9729/Algorithm

Level 2 - 124 나라의 숫자

사용 가능한 숫자는 1,2,4 총 3개 뿐이다. 자연스럽게 3진법이 떠오른다. 좀 더 쉽게 생각하기 위해 4대신 3이 있다고 생각한다. 현재 사용 가능한 숫자는 1,2,3이다. 

 

자연수를 3진법으로 변환한다면 0,1,2만 사용되며 한 자리에 최대 2까지 표현할 수 있다. 단 문제의 경우 1,2,3만 사용되며 한 자리에 최대 3까지 표현할 수 있다. 중요한 점은 한 자리에 최대 3까지 표현 가능하다는 점이다. 예를 들어 자연수 6을 원래 3진법으로 변환하면 "20"이다. 하지만 한 자리에 3까지 표현 가능하다면 "13"으로 변환된다. 즉 원래 3진법에서 사용되는 0을 한 단계 높은 자리의 숫자에서 1을 뺏어와 3으로 표현한다. 이렇게 생각하고 다시 변환해보자.

 

자연수 9를 3진법으로 변환하면 "100"이다. 이를 위에서 말한 방법으로 해당 문제에서 원하는 숫자로 변환해본다. 두번째 자리의 숫자 0을 한 단계 높은 자리의 숫자에서 1을 뺏어와 3으로 표현한다. 그러므로 숫자는 "30"으로 변환된다. 다시 첫 번째 자리의 숫자 0을 한 단계 높은 자리의 숫자에서 1을 뺏어와 3으로 표현한다. 그러므로 숫자는 "24"이다. 

 

이 방법으로 자연수를 3진법으로 변환한다. 입력받은 자연수 n에 대해서 n이 만약 3의 배수라면 3을 추가하고 n을 3으로 나누고 1을 뺀 수로 변환한다. 만약 n이 3의 배수가 아니라면 원래의 3진법 방법대로 변환한다. 

 

마지막으로 문제에서 사용가능한 숫자는 1,2,4이므로 n이 3의 배수일 때 3이 아닌 4를 추가한다. 

#Level 2 124 나라의 숫자.py
def solution(n):
    answer = ''
    num = []
    while n != 0 : 
        if n%3 == 0 : 
            num.append("4")
            n = n//3 -1
        else : 
            num.append(str(n%3))
            n = n//3
    answer = "".join(reversed(num))
    return answer