백준 1436번 영화감독 숌 - 스위프트(Swift) 풀이

 먼저 브루트포스로 가능한 지부터 고려해야 한다. 1, 2, 3... 이렇게 1부터 차례로 666이라는 수를 포함하는지 체크해서 N번째로 666을 포함하는 수를 만나면 출력하고 break 해주면 간단하게 구할 수 있을 것이다. 이 방법이 제한 시간 안에 통과되는지 계산해보자.

 일단 N의 최대값이 10,000이다. N = 10,000일 때 답이 몇 일지 예상해야 한다. (예상 못하겠으면 그냥 N=10,000으로 두고 위에 반복문 돌려서 기다려보면 알 수 있긴 하다.) 대충 666이 맨 끝에 오는 경우만 생각해줘 봤는데, 10,000가지가 되려면 채우려면 666 앞에 4자리가 더 붙어야 한다. _ _ _ _ 666 이렇게 되면 각 자리마다 0-9가 들어갈 수 있으니까 10,000가지가 될 것이다. 따라서 N = 10,000일 때 답은 적어도 10,000,000보다는 작다고 생각할 수 있다.

 그럼 이제 숫자 하나에 대해 666이라는 수를 포함하는지 여부를 검사하는데 걸리는 시간 복잡도를 계산해보자. 예를 들어 46,665라는 숫자를 검사한다고 하자. 맨 뒤부터 차례로 666을 포함하고 있는지 체크할 것이다. 1000으로 나눴을 때 나머지가 666인지 체크, 이후 10으로 나눈 후 다시 1000으로 나눠서 나머지 체크.. 를 반복하면 된다. 46,665 % 1000 = 665이고, 이제 맨 뒤 자리를 날리기 위해 10으로 나눠주면 4,666이 된다. 다시 4,666 % 1000 = 666, 666을 포함한다는 것을 알아냈다. 이렇게 하면 해당 수의 자릿수만큼의 탐색이 필요하게 된다.

 최대로 고려해야 하는 수가 10,000,000보다 작으므로 7자리 수일 것이므로 최대 연산은 70,000,000번의 정도로 추정할 수 있다. 대략 1,000,000,000번의 연산을 1초로 어림잡을 수 있으므로 제한 시간인 2초 안에 돌아갈 것이다!

 

 어차피 N=1일 때 답이 666이므로 for문은 666부터 돌아도 된다.

import Foundation

let N = Int(readLine()!)!

var count = 0
for i in 666...10000000 {
    var n = i
    while n >= 666 {
        if n % 1000 == 666 {
            count += 1
            break
        }
        n /= 10
    }
    
    if count == N {
        print(i)
        break
    }
}