저주의 숫자 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 마을에서 몇 번째 숫자까지 찾았는지를 나타내고, currentNumber는 우리가 현재 검사 중인 일반 숫자를 나타낸다.

class Solution {
    public int solution(int n) {
        int count = 0;
        int currentNumber = 0;
 
        while (count < n) {
            currentNumber++;
 
            if (currentNumber % 3 != 0 && !String.valueOf(currentNumber).contains("3")) {
                count++;
            }
        }
 
        return currentNumber;
    }
}

조건을 분리해서 보기

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

currentNumber % 3 != 0 && !String.valueOf(currentNumber).contains("3")

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

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

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

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

단순한 풀이가 충분한 이유

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