[Python3] 프로그래머스 | 코딩테스트 연습 -> 연습문제 -> 124 나라의 숫자

코딩테스트를 준비하며 문제를 풀다, 오랜시간 고민한 문제라서

아주 오랜만에 포스팅 한다.

 

우선, 처음에는 3진법으로 접근하고자 하였다. 

10진법 -> 2진법을 구하는것처럼, 

n진법일 경우, n으로 나눈 몫과 나머지를 활용하는 방안을 생각하였다.

 

이 경우, 3진법은 (0, 1, 2)를 사용하기 때문에 3(10진수) = 10(3진수)가 된다. 

이렇게 생기는 10(3진수)를 4로 바꾸면 되겠다는 생각을 하였다.

 

중간에 1로 자리가 올라가는 숫자를 생각하지 못하고 0만 4로 바꿔서 많이 해맸다.

10(3진수)를 4로 바꾸기 위해선,

3으로 나눈 나머지가 0일때, 올라가는 수인 1을 빼주어야 한다.

이것은 3으로 나눈 몫에서 1을 빼주는것과 같다.

또한, 0을 4로 바꾸어 문자열에 넣어준다.

 

아주 어릴때 배웠던 빼기 계산에서 빼고자 하는 자릿수의 수가 작아서 못빼면,

윗자리 숫자를 빌려오는 개념과 비슷하다..!

몫에서 1을 빼주는 대신, 나머지에 3을(124나라니까 4를) 넣어주는 것이라고 보면 된다. (나머지가 3이라는것은 나누어떨어진다는것이니까 나머지가 0이 나온다. 즉, 나머지가 0이면 4로 바꾸고, 다음 몫에서 1을 빼주면서 계산을 하면 된다.)

문제를 다 푼 뒤에도, 정확도는 모두 통과했지만, 효율성에서 하나의 케이스를 통과하지 못했다.

불필요한 것들을 모두 제거하고 간결하게 표현하니, 통과하였다.

 

아래는 내가 쓴 코드이다.

 

def solution(n):
    answer = ''
    
    while True:
        # print('->', n)
        if n==0:
            break
        
        if n%3==0:
            answer += '4'
            n = n//3 - 1
        else:
            answer += str(n%3)
            n = n//3
    
    answer = ''.join(reversed(answer))
    # print(answer)
    
    return answer