[프로그래머스][PYTHON] Lv. 0 저주의 숫자 3

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/120871#

프로그래머스

 

 

 

내 풀이

def solution(n):

    cnt = 0
    # new_num 리스트에 3x 마을에서 사용하는 숫자들을 담음
    new_num = []
    # 10진법 숫자는 100까지 사용되므로, 3x 마을에서 사용하는 숫자 개수도 100개 담음
    while len(new_num) < 100:
        cnt += 1
        # 숫자에 3이 포함되지 않거나 3의 배수가 아닐때..
        if '3' not in str(cnt) and cnt%3 != 0:
            new_num.append(cnt)

    return new_num[n-1]

 

처음에는 규칙이 있는줄 알고 이를 통해 풀려했다. 

"""
1   1           3*0+1   n
2   2           3*0+2   n
3   3+1         3*1+1   n+1
4   3+2         3*1+2   n+2
5   3+3+1       3*2+1   n+2
6   3+3+2       3*2+2   n+2
7   3+3+3+1     3*3+1   n+3
8   3+3+3+2     3*3+2   n+3
9   3+3+3+3+2   
"""

 

근데, 처음 몇 개의 숫자에서는 규칙이 있어보였는데,, 생각해보니 숫자가 점점 커지면 일정한 규칙이 사라지는 것을 발견했다.

따라서 그냥 제한된 숫자가 1<=n<=100이므로 그냥 제한된 모든 경우를 생각해보기로 하였다. 

 

먼저,  new_num 리스트를 새로 만든다. 

이 리스트에는 일반적인 10진법 수에 대응되는 3x마을의 숫자만을 담는다! 

 

10진법 수는 100까지만 나오므로, 3x마을의 숫자도 100개만 가정하면 되기 때문에 while문을 통해 제한한다. 

이때, 10진법 수를 기준으로 1부터 세면서, 숫자에 3이 포함되지 않거나 3의 배수가 아닐 때 3x 마을의 숫자로 정의한다. 

 

최종적으로 new_num 리스트에는 1부터 차례대로 100개의 새로운 숫자가 담기게 된다! 

즉, new_num = [1, 2, 4, 5, 7, 8, 10, 11, 13, 16, ...]

이후, 주어진 숫자 10진법 수의 인덱스에 맞춰 new_num을 접근하면 

10진법 수에 대응되는 3x마을의 숫자를 알 수 있다. 

 

 

다른 사람 풀이

def solution(n):
    answer = 0
    for _ in range(n):
        answer += 1
        while answer % 3 == 0 or '3' in str(answer):
            answer += 1
    return answer

 

나와 비슷한 풀이이다. 

이 풀이는 제한된 모든 수를 지정하지 않고, 원하는 숫자까지의 for문을 돌며

이를 3x마을의 숫자로 바꾸는 것이다. 

 

for문을 돌며, 현재 answer을 1씩 증가시키는데,

이 때 현재 answer이 3의 배수이거나 숫자 3을 포함한다면 answer + 1을 반복하여 원하는 숫자를 찾는다. 

이를 answer로 바꿔가며 계속 숫자를 구해가는 풀이이다. 

 

느낀점

내가 한 풀이는 나중에 숫자의 제한범위가 커지면 시간초과가 날 것 같다. 

필요한 범위만 지정하여 생각해보는 풀이 방법이 더 좋은듯하다.