프로그래머스 level2 - 124 나라의 숫자

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법	124 나라
1	1
2	2
3	4
4	11
5	12
6	14
7	21
8	22
9	24
10	41

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 50,000,000이하의 자연수 입니다.

입출력 예

n	result
1	1
2	2
3	4
4	11

문제 풀이

def solution(n):
    answer = []
    # n이 0 즉, False가 될 때까지
    while n:
        # n을 3으로 나눈 나머지
        n1 = n % 3
        # n이 3으로 나누어 떨어지면
        if not n1:                    
            # 4로 올리고 몫에서 1을 뺌
            # 3진법으로는 0이 와야하지만 4를 추가하여 맞춰주기 위함
            n1 = 4
            n -= 1                        
        answer.append(str(n1))
        n //= 3

    return ''.join(answer[::-1])

 

 

 

123 나라의 표현 법은 3진법에 기반을 한다. 3진법은 0, 1, 2로 표현을 해야하고 124 나라는 1, 2, 4로 표현을 해야한다. 

해당 코드에서 의아한 부분이 n -= 1 즉 몫에서 1을 빼주는 부분일텐데 이유는 다음과 같다.

만약 124 나라가 아니라 123 나라였다면 추가로 처리할 부분은 없었을테지만 3을 건너뛰고 1 2 4만 사용하여 표현해야한다. 3진법의 0이 와야할 자리에 4를 넣어야하기 때문에 몫에서 1을 빼주어 자리올림 처리를 해주기 위함이다.

즉, 3진법의 0을 4로 바꾸기 위해선 그 자리에 3을 만들고, 그 이후에 1을 더해줘야하기 때문이다. 따라서 3진법에서 0이 나왔을 때 그 자리를 4로 만들기 위해 나머지 연산에서 -1을 해준다.

시간 복잡도

• while n 루프로 n이 0이 될 때까지 실행.
  • n % 3, n //= 3 연산이 한 번씩 수행
  • n -=1은 조건에 따라 한 번만 수행
  • answer.append() 한 번의 반복마다 리스트에 추가
• n을 3으로 계속 나누기 때문에 반복 횟수는 O(log₃ n). 로그의 밑이 3일 때, O(log n)와 동일한 시간 복잡도를 가지기 때문에 전체 시간 복잡도는 O(log n)

공간 복잡도

• answer 배열의 크기는 n을 3으로 나누었을 때 필요한 자릿수만큼 커지기 때문에 전체 공간 복잡도는 O(log n)

실행 결과

 

 

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