[프로그래머스] #lv.2 - 124 나라의 숫자 (Python)

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

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

 

접근법

핵심 아이디어

• 3진법
• 10진법을 N진법으로 변환할 때, 나머지-> 몫 순으로 표시 (출력을 거꾸로)
• 3진법 변환과 124 변환의 차이점 이해 (핵심)

 

우선, 3진법을 떠올려야 한다.

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

 

3진법은 3을 표현할 때 숫자 0을 사용하는 반면, 124 나라는 4라는 추가 숫자를 사용해서 표현한다.

 

이걸 유의하면서 접근하면 n이 3으로 나눠지면 (나머지가 0이면) '4'를 문자열에 추가하고,

그러지 않을 경우는 n을 3으로 나눈 나머지를 문자열에 추가하면 된다.

 

(진수 변환 규칙 : 나머지들을 먼저 추가하고 마지막에 남은 몫을 추가)

# 3진법 변환

n = 5:

5 // 3 = 1, 나머지 = 2, 현재답 : '21' -> '12' 출력

 

n = 6:

6 // 3 = 2, 나머지 = 0, 현재답 : '02' -> '20' 출력

 

n = 9:

9 // 3 = 3, 나머지 = 0, 다음 n = 3, 현재 답 : '0'

3 // 3 = 1, 나머지 = 0, 현재답 : '001' -> '100' 출력

 

비슷하게 124 변환을 해본다.

 

# 124 변환

n = 6:

6 // 3 = 2, 나머지가 0이므로 현재답 : '4'

2 // 3 = 0, 나머지 = 2, 현재답 : '420'

?? 우리가 예상한 답('41')과 다르다.

 

n = 9:

9 // 3 = 3 나머지가 0이므로 현재답 : '4'

3 // 3 = 1, 나머지 = 0, 현재답 : '441'

?? 우리가 예상한 답('42')과 다르다.

 

3진법 변환과 동일한 로직으로 124 변환을 실행한 결과, 기대값과 결과값이 다른 걸 확인할 수 있다.

따라서 124 변환의 추가 규칙을 찾을 필요가 있다.

 

숫자를 적으면서 쭉 나열해 보면, 3의 배수만 124 변환에 문제가 있음을 알 수 있다.

따라서 3으로 나눠지는 경우 추가적인 작업을 해줘야 한다는 뜻이다.

 

결과적으로, 3으로 나눠지는 경우 다음 연산에 사용될 몫에 1을 빼주는 연산을 해줘야 한다.

왜 이런지는 참 이해하기 어려운데, 이건 3진법과 124 변환의 차이점에서 발생한 일종의 규칙이다.

 

# 124  변환

n = 6:

6 // 3 = 2, 나머지가 0이므로 현재답 : '4'

몫 - 1

1 // 3 = 0, 나머지 = 1, 현재답 : '41' -> '14'

 

n = 9:

9 // 3 = 3 나머지가 0이므로 현재답 : '4'

몫 - 1

2 // 3 = 0, 나머지 = 2, 현재답 : '42' -> '24'

 

왜 이런 규칙이 생겨난 걸까??

 

원인은 자릿수가 증가하는 시기의 차이 때문이다.

3진법은 3의 배수에서 자릿수가 증가하는 반면, 124 나라는 4까지 사용하기 때문에 3의 배수 +1 수에서 자릿수가 증가한다. (그래서 이를 보정하기 위해 몫에서 1을 빼는 것 같다. 정확한 수학적 원리는 이해하지 못했다.)

 

따라서 3으로 나누어지는 경우 다음 연산에 이용할 몫에 1을 빼서 적용해 줘야 우리가 원하는 대로 변환을 할 수 있다.

(물론 이를 직관적으로 떠올리기는 굉장히 어렵다.)

 

결론 : 3의 배수일 때, 몫-1 규칙을 찾기

 

 

정답 코드 (파이썬)

def solution(n):
    answer = ''
    while n:
        if n % 3 == 0:
            answer += '4'
            n -= 1
        else:
            answer += str(n%3)
        n //= 3
    return answer[::-1]

 

여담

3의 배수일 때 몫에 -1을 해주는 규칙이 참 와닿지 않는다. 레벨2 치고는 많이 어려운 것 같다.