[Programmers] 124 나라의 숫자 (Python)

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

 

1, 2, 4만 있는 나라에서 10진수를 어떻게 표현할  수 있는가? 라는 문제!

처음 딱 봤을 때 3진법으로 나타내고 0, 1, 2를 각각 매칭해주면 되겠네! 라고 간단하게 생각했다.

그러나 풀어서 생각해보니

0의 경우 단독으로 맨 앞자리에 올 수 없으므로 단순 매칭으로는 해결할 수 없다는 문제가 있었다!

 

숫자를 다 나열해서 비교해보며 찾아낸 규칙은

1. 3으로 나누어 떨어지지 않으면 3진법으로 나타낸 수를 그대로 사용하고

2. 3으로 나누어 떨어지는 경우 4를 대신 넣어주고, n // 3 -1 에서 이어서 계산을 해주면 된다.

 

이렇게 두 가지였다!

이러한 규칙만 찾아내면 간단하고, 입력으로 주어지는 숫자가 아무리 커도 시간 효율성도 따로 고려하지 않아도 충분히 계산 가능이다!

 

 

def solution(n):
    answer = ''
    while n :
        if n % 3 != 0 : # 3으로 안나누어떨어지면
            answer += str(n % 3)
            n //= 3
        else :
            answer += "4"
            n = n // 3 - 1
    return answer[::-1]