백준 1436 - Swift

 

백준 1436

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

 

 

 

문제 이해)

맨 처음에 문제를 읽었을 때는 그냥 N-1해서 666 붙이면 되는거 아닌가? 했는데 아닙니다..

N번째를 포함한 영화 제목을 찾아야 하는 문제였어요.

즉, N이 입력되면 N이 들어가는 영화의 제목을 출력하는 것 2번째 영화가 아니라 N이 들어가는 영화의 제목을 출력 하는 것

 

쉽게 풀어보자면,

첫 숫자가 666이 되고, 666 += 1 씩해가면서 666이 연속으로 나오는 것을 찾아야 합니다.

N = 2라면 666 +=1 을 했을 때 667~900까지 없고 1590없고,

1600없다가 1666에서 숫자 N인 1을 발견! 그래서 리턴값이 1666이 되는 패턴입니다.

 

 

브루트포스 분류에 있는 만큼 완전 탐색을 통해서 쉽게 풀 수 있어요.

for을 통해서 666부터 시작해서 += 1 해가면서 찾는 코드와

while문을 통해서 count가 N과 같을 때까지를 체크해가면서 찾는 코드

 

방법은 동일하지만 for / while 문을 통해서 작성했어요.

올바르게 동작하지만, 시간 초과가 계속 나서 이리저리 헤맸습니다...

 

let n = Int(readLine()!)!

func solution1(n: Int) -> Int {
    var count = 0
    var num = 665

    while count < n { // 숫자를 계속 증가시키면서 666이 나오는 횟수가 N과 같을때까지
        num += 1 // 영화는 0번째가 없으니까 count를 1로 해놓고 시작
        
        if(String(num).contains("666")) {
            count += 1
        }
    }

    return num
}

func solution1(n: Int) -> Int {
    var count = 0
    var num = 0
    
    for i in 666... {
        if String(i).contains("666") {
            count += 1
            
            if count == n {
                num = i
                break
            }
        }
    }
    
    return num
}

print(solution1(n: n))
print(solution2(n: n))

Int -> String -> Contains가 선형적으로 증가하는 패턴에다가

10,000 까지 제한이 있다보니, 10,000이 입력됐을 경우에 정답은 1,000,000이 넘게 나오는데

200번만 반복해도 제한시간을 넘어가버리니.. 시간 초과가 나는 것 같더라구요.

 

 

그래서 나머지 연산을 통해서 빠르게 연산 횟수를 줄이는 방법으로 다시 구현했습니다.

func soluton3(n: Int) -> Int {
    var count = 0
    var num = 0
    
    while count != n { // count = n일때까지
        var temp = num
        
        while temp >= 666 {
            if temp % 1000 == 666 { count += 1; break } 
            else { temp /= 10 }
        }
        
        num += 1
    }
    
    return num-1
}

왜 temp /= 10이냐면

나머지 계산을 했을 때 666이 아니면 마지막 자리 숫자를 버리면서 계산하면 되기 때문에

(숫자가 몇일 줄 예상을 못하기 때문에 첫번째를 버릴 순 없으니..)

10을 해야 패턴에 알맞는 숫자를 찾을 수 있습니다.

 

 

 

문제 이해부터 시간초과까지 실버5치고 꽤나 애먹었던 문제네여..

끝!