[Programmers] #120871 - 저주의 숫자 3 [Java][C++][Python]

문제 링크

---

1. 아이디어

3x 마을 사람들은 3을 저주의 숫자라고 생각해서 3의 배수와 3이 들어가는 수는 건너뛰고 수를 센다. 따라서 1부터 3x 마을에서 사용 가능한 수가 등장할 때마다 카운팅을 해서 n이 될 때까지 센 후 이를 반환하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \times D)$	$O(D)$

($N$ = 입력값 n, $D$ = 결과값의 자릿수 $\approx \log_{10} N$. 반복마다 현재 수를 문자열로 바꿔 3 포함 여부를 확인)

---

3. 코드

풀이 [Java][C++][Python]

3의 배수는 모듈러 연산으로, 3이 들어가는지는 문자열 변환 후 3을 포함하는지 여부로 판정했다.

class Solution {
    public int solution(int n) {
        int x = 0;
        int cnt = 0;
        while (cnt < n) {
            x++;
            if (x % 3 == 0 || String.valueOf(x).contains("3")) continue;
            cnt++;
        }

        return x;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(int n) {
    int x = 0;
    int cnt = 0;
    while (cnt < n) {
        x++;
        if (x % 3 == 0 || to_string(x).find('3') != -1) continue;
        cnt++;
    }

    return x;
}

def solution(n):
    x, cnt = 0, 0
    while cnt < n:
        x += 1
        if x % 3 == 0 or "3" in str(x):
            continue
        cnt += 1

    return x

---