[바미] 영화감독 숌

문제

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

---

코드 및 코드 설명

function findNthTitle(n) {
    let count = 0; // 666을 포함하는 숫자의 개수를 세기 위한 카운터
    let num = 666; // 종말의 수 검색을 시작할 값

    while (true) {
        if (num.toString().includes('666')) { // 숫자를 문자열로 변환하여 '666'이 포함되어 있는지 확인
            count++; // '666'을 포함하면 카운트 증가
            if (count === n) { // 만약 카운트가 입력된 N과 같아지면
                return num; // 현재 숫자를 반환
            }
        }
        num++; // 다음 숫자로 이동
    }
}

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const n = parseInt(input, 10);
console.log(findNthTitle(n)); // 함수 호출 및 결과 출력

findNthTitle 함수는 N을 매개변수로 받아 N번째 종말의 수를 찾아 반환하는 함수입니다.
count 변수는 '666'을 포함하는 숫자의 개수를 세기 위해 사용되는데 이 변수는 0에서 시작하여, '666'을 포함하는 각 숫자를 발견할 때마다 1씩 증가합니다.
num 변수는 666부터 시작하여, 각 숫자가 '666'을 포함하는지 검사하며 '666'을 포함할 때마다 num은 1씩 증가합니다.

while 루프 내에서, num.toString().includes('666')를 통해 각 숫자가 '666'을 포함하는지 검사합니다. N번째 '666'을 포함하는 숫자를 찾으면, 그 숫자를 반환하고 함수는 종료됩니다.

문제 풀이

이 문제는 "666"이 포함된 수를 순서대로 찾아서 N번째 값을 출력하는 문제입니다. 주어진 숫자 N에 대해 N번째로 작은 "666"을 포함하는 수를 찾아야 합니다.

 

그래서 특정 패턴("666"이 연속으로 나타나는 것)을 포함하는 N번째 숫자를 찾기 위해서는 모든 숫자를 순차적으로 검토하는 것이 가장 직접적이고 확실한 방법이기 때문에 브루트 포스(Brute Force) 접근 방식을 사용하여 풀어줍니다.

시간 복잡도

이 알고리즘은 각 숫자를 순차적으로 확인하며, "666"이 포함되어 있는지 검사합니다.

이 때, N이 크면 클수록 더 많은 숫자를 확인해야 하며, 각 숫자가 "666"을 포함하는지 검사하는 데 필요한 시간은 숫자의 길이에 비례합니다.

 

그래서 평균적으로 숫자의 길이가 늘어남에 따라 검사 시간도 증가하지만, 이 문제에서 시간 복잡도를 정확히 계산하는 것은 복잡합니다. 그러나 이 방법은 "666"이 포함된 수를 찾기 때문에 일반적으로 O(N×M)이 됩니다.

여기서 M은 숫자를 문자열로 변환하고 검사하는 데 필요한 평균 시간을 의미합니다.

공간 복잡도

이 알고리즘은 count와 num 두 개의 변수만을 사용하여, 추가적인 공간을 거의 사용하지 않습니다. 따라서 공간 복잡도는 O(1)입니다. 입력 크기나 출력 크기와는 독립적입니다.

 

코드 자체가 간단하고 직관적이지만, N의 값이 매우 클 경우 많은 숫자를 검토해야 하므로 시간이 오래 걸릴 수 있다는 점이 있습니다. 이러한 점은 브루트 포스 접근법의 일반적인 단점이라 생각해주시면 됩니다.