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

문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요. 제한사항 n은 500,000,000이하의 자연수 입니다.

 

---

124 숫자의 규칙을 그려본 결과 재귀패턴이 반복되고 있었다.

일단 문자열 재귀패턴 규칙으로 그대로 밀어붙여보았다 거기서 멈췄어야 했는데

 

 

1차 답안

- 참고로 효율성에서 장렬히 망한 풀이다.

cnt = 0
nums = '124'

def recursive(pre,n):
    global cnt
    result = []
    for num in nums:
        for p in pre:
            result.append(num+p)
            cnt += 1
            if cnt == n:
                return result[-1]
            
    return recursive(result,n)
    
    
def solution(n):
    if n < 4:
        return str(nums[n-1])
    else:
        global cnt
        cnt += 3
        return recursive(nums,n)

 

정확성 테스트만 다 통과하면 뭐하나~~ 효율성에서 망했다

아마 이건 자잘한거 튜닝해봐야 소용 없다.. 어딘가 구조 자체가 틀려먹은거다

 

생각해보니 수를 다루는 문젠데 너무 문자열 관점으로 접근한것 같다

 

---

 

3진법으로 생각을 틀어보았다.

0,1,2 와 달리 문제가 요구하는건 1,2,4 다.

나머지 1,2 까지는 기존 3진법과 다를바가 없다. 근데 문제는 0인 경우에 10이 아니라 4가 되어야 한다.

 

총 두가지 방법이 있다.

 

첫 번째

- 나머지 0인 경우만 예외처리하는 것에 집중한 방식

def solution(n):
    answer = ''
    
    while n:
        n,r = divmod(n,3)
        answer = '412'[r] + answer
        if not r:
            n -= 1
            
    return answer

• 나머지 0인 경우 4이므로, 아예 412 배열로 두고 계산하는 방식이다.
• 나머지 0일 때 몫을 1 빼는 경우는.. 직관적으로 이해하기 보다는 손으로 코드 과정을 따라가보면 깨닫게 될텐데
• 예를 들어 ~ n=3인 경우,  answer에 4를 넣고 끝내야 하는데 몫이 0이 아닌 1로 잘리다 보니 반복문이 안 끝나는 문제가 생긴다.
• 이 때 1을 빼줘야 코드가 오작동을 안한다.

나도 몫을 1 빼줘야 한다는건 에러로 부닥쳐보면서 알았다...

이걸 바로 캐치할 수 있을 정도가 되려면 수많은 노력이 필요한 것 같다

 

그리고 다른 사람들의 풀이를 보면서 발견한, 더 간단하고 이해하기가 더 힘겨웠던 방식이 있다.

 

 

두 번째

- 자릿수가 변하는 지점이 1씩 밀리는 점을 이용한 방식 극한의 숏코딩

def solution(n):
    answer = ''
    
    while n:
        n,r = divmod(n-1,3)
        answer = '124'[r] + answer
            
    return answer

 

언뜻 보면 첫번째와 상당히 비슷하다.

간단하지만 큰 차이점이 있다.

 

1. 첫번째와 달리, 모든 경우에서 n을 1씩 빼주고 있다.

2. 숫자 배열이 '412' 가 아닌 '124' 그대로다.

 

n을 왜 모든 경우에 빼주는지 힘겹게 이해한걸 정리해보겠다.

 

10진법 6,7,8의 경우를 예로 들어보자.

원래 3진법이라면 3의 배수마다 앞자리가 변하게 되어있다.

그런데 위 TC 테이블로 봤을 때, 7부터 바뀌고 있다.

 

-> 즉, 1씩 자릿수 변경 구간이 밀려있다.

3진법에서 나머지 2가 되는, 즉 자릿수 변경 전 마지막 수가 되는 구간이 5가 아닌 6이 되어있다.

 

결론은, 진법 계산 공식을 조금 다르게 이해해야한다.

7의 경우를 7 = 3^1*2 + 3^0*1 로 오리지널 3진법으로 볼게 아니라,

1을 뺀 수(6)의 몫과 나머지로 3진법을 구하는 과정에서

나머지 [0,1,2] 를 [1,2,4] 에 대입시켰다고 봐야 한다.

 

내가 쓰면서도 어려워서 아마 이틀 뒤 다시보면 뭔소린가 할지도 모르겠다...

추상화해서 말하자면 하나씩 밀렸으니 이전꺼를 갖다 쓰는 로직이라고 보면 된다.

 

이 방식의 장점은 비슷한 다른 문제가 나왔을 때 좀더 범용성 있게 적용할 수 있다는 것 같다.

비슷한 유형의 진법 문제가 나왔을 때, 얼마나 밀렸는지 확인해보고 몫을 빼준 다음, 테스트 케이스와 동일하게 결과가 나오는 공식을 도출하는 식으로 적용할 수 있...긴 한데

 

사실 이걸 바로 떠올린다는게 쉬운 일이 아니다. 공식은 간단하지만 숫자 간 서로 유기적인 관계를 완벽히 캐치해야 한다.

더군다나 시간적 압박이 있는 환경이라면.. 이렇게 깔끔한 코드도 좋지만 로직을 생각해내기도 어렵고 받아들이는데도 시간이 걸린다. 가장 깔끔한 방식까진 아니더라도, 쓸 수 있는 규칙을 도출해내는데 집중하자.