124 나라의 숫자

프로그래머스

---

 

처음에는 n의 124 나라에서의 숫자의 자리수를 구한 후, 해당 자리수만큼 중복순열(product)를 사용해 리스트를 만든 후, 

해당 리스트의 인덱스에 해당하는 수를 리턴하도록 했다.

이러면 내가 구하려는 수 말고도, 자리수에 해당하는 124 나라에서의 모든 수를 구해야 하므로 쓸 데 없는 계산을 많이 해, 시간 초과가 뜬다.

 

시간 초과 풀이

from itertools import product

def solution(n):
    answer = ''
    
    i = 3
    cnt = 1 # 자리수
    while True:
        if n - i > 0:
            n -= i
            cnt += 1
            i = 3 ** cnt
        else:
            break
            
    nums = ["1", "2", "4"]
    cand = sorted(list(product(nums, repeat = cnt)))

    return "".join(cand[n-1])

 

 

---

다시 한 번 천천히 생각해보니 규칙을 찾을 수 있었다.

1 -> 4, 5, 6

의 경우를 보면 1 다음에는 3 * 1 + 1, 3 * 1 + 2, 3 * 1+ 3의 수가 이어지게 된다.

 

1 -> 4, 5, 6 -> 13, 14, 15, 16, 17, 18, 19, 20, 21

 

이 경우에서 같은 색깔은 모두 같은 식이 적용되는 걸 확인할 수 있다.

즉, a라는 수 다음에는 3 * a + 1, 3 * a + 2, 3 * a + 3이 이어지고, 그 다음에도 또 같은 식이 이어진다.

 

이런 일반식을 통해 답을 구할 수 있다.

 

 

풀이

def solution(n):
    answer = ''
    numbers = ["4", "1", "2"]
    
    while n >= 1:
        index = n % 3
        answer += numbers[index]
        # 만약 n이 3으로 나눠 떨어지면 1을 추가로 빼준다.
        if n % 3 == 0:
            n = n // 3 - 1
        # n이 3으로 나누어 떨어지지 않는 경우에는 그냥 3으로 나눈다.
        else:
            n = n // 3
    
    # 순서를 뒤집어야 정답
    return answer[::-1]

 

numbers 리스트에 ["4", "1", "2"]를 넣는다.

그리고 반복문을 돌면서 n을 3으로 나눈 나머지를 인덱스로 해서 answer에 numbers[index]를 더한다.

그리고 n이 3으로 나눠떨어지는 경우에는 n을 3으로 나누고 1을 더한다.

그리고 n이 3으로 나눠떨어지지 않는 경우에는 n을 3으로 나눈다.

n이 1 이상일 경우까지 반복한 후, 추가된 answer를 뒤집으면 답이 나온다.

 

규칙을 찾으면 쉽게 풀 수 있지만 찾지 못한다면, 풀기 어려운 문제.

여러 문제를 경험해보는 게 답인 것 같다.