저주의 숫자 3

이 문제는 3x 마을에서 쓰는 숫자를 구하는 문제다. 3x 마을에서는 3의 배수와 숫자 3이 들어간 수를 사용하지 않는다. 그래서 우리가 아는 자연수의 순서와 3x 마을의 숫자 순서가 달라진다.

예를 들어 일반적인 숫자에서는 1, 2, 3, 4, 5처럼 이어지지만, 3x 마을에서는 3을 건너뛰어 1, 2, 4, 5, 7처럼 이어진다. 3, 6, 9처럼 3의 배수도 빠지고, 13, 23, 30처럼 숫자 3이 포함된 수도 빠진다.

하나씩 세는 방식

문제를 푸는 가장 단순한 방법은 실제로 숫자를 하나씩 올려보면서 조건을 만족하는 숫자만 세는 것이다. count는 3x 마을에서 몇 번째 숫자까지 찾았는지를 나타내고, current는 우리가 현재 검사 중인 일반 숫자를 나타낸다.

def solution(n):
    count = 0
    current = 0
 
    while count < n:
        current += 1
        if current % 3 != 0 and '3' not in str(current):
            count += 1
 
    return current

조건을 분리해서 보기

핵심 조건은 두 가지다. 먼저 3의 배수가 아니어야 한다. 그리고 숫자를 문자열로 바꿨을 때 3을 포함하지 않아야 한다.

current % 3 != 0 and '3' not in str(current)

이 조건을 통과한 숫자만 3x 마을에서 사용하는 숫자이므로 count를 하나 올린다. count가 n이 되는 순간의 current가 정답이다.

n = 15라면 조건을 만족하는 숫자는 다음처럼 세어진다.

1, 2, 4, 5, 7, 8, 10, 11, 14, 16, 17, 19, 20, 22, 25

15번째 숫자는 25이므로 결과는 25다. n = 40일 때는 같은 방식으로 계속 세면 76이 나온다.

단순한 풀이가 충분한 이유

처음에는 규칙을 수식으로 바꿔보려 할 수 있지만, 이 문제에서는 숫자에 3이 포함되는 조건 때문에 단순한 나눗셈만으로 처리하기 어렵다. 이 문제의 입력 제약은 n ≤ 100이라, 하나씩 검사하면서 유효한 숫자만 카운트하는 방식이 가장 읽기 쉽고 실수도 적다.

반복 횟수는 n이 아니라 정답 값 k에 비례한다는 점은 짚고 넘어갈 만하다. n = 15일 때 답이 25이므로 25번 돈다. 건너뛰는 수가 있어서 k는 항상 n보다 크고, 반복마다 str(current) 변환에 자릿수만큼의 비용이 더 붙는다. n이 100 정도면 아무 문제가 없지만, 제약이 수억 단위였다면 이 방식 그대로는 못 쓰고 규칙을 이용한 계산으로 바꿔야 한다. 제약을 먼저 보고 풀이의 상한을 정하는 습관이 여기서도 통한다.