[BOJ] 백준 1436 영화감독 숌 (Swift)

문제

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

1436번: 영화감독 숌

풀이

맨처음에는 DP를 떠올렸다가.. 점화식을 구하는데 애를 먹어서 일단 완전탐색으로 접근하였습니다.
666부터 1씩 증가시켜서 6이 연달아서 3번 등장한다면, 배열에 넣어주고 입력받은 n - 1번째 요소를 출력해주었습니다.

그런데...

여기서 저는 String의 contains 메서드를 사용하여 "(number)".contains("666") 과 같이 사용하였는데
Int -> String -> Contains 때문인지.. 시간초과가 발생하였습니다.

이 Int 자료형에 666이 등장하는지 확인하기 위해
Int를 1000으로 나눈 나머지가 (뒷자리 3자리 수만 남기기 위해) 666이라면, 6이 연속으로 3번 등장한것이 되겠죠?
아니라면, Int를 10으로 나누어 버리면 맨 뒷자리 1자리 수가 줄어들게 됩니다.

예를들어 1266612 라는 수가 있다고 가정하면,

• 1266612 % 1000 = 612 (X)
• 1266612 / 10 = 126661
• 126661 % 1000 = 661 (X)
• 126661 / 10 = 12666
• 12666 % 1000 = 666 (O)

666이 등장하는 것을 확인할 수 있습니다.

이것을 Int의 Extension으로 작성해주었고, while문으로 Int가 666보다 클 때만 반복하도록 작성해주었습니다.

이제 666부터 1씩 증가시켜보면서 666이 등장한다면 배열에 넣어주고, index를 1씩 늘려줍니다.
index가 입력받은 n과 같아진다면, n번째 등장하는 수를 찾은 것이므로
배열의 n - 1번째 인덱스를 갖는 요소를 출력해주면 됩니다.

소스코드

후기

앞으로 Int 자료형을 자릿수별로 하나씩 순회하거나, 검사하는 경우
String 자료형으로 형변환을 하는 것이 아닌, 나누기 등의 연산을 통해서 사용하는 것이 더 빠르다는 것을 알게되었습니다.

DP를 먼저 떠올렸지만, 점화식을 구하지 못해 일단 완전탐색으로 풀어보고, 예제 출력이 얼마나 클지 확인해보니
n이 최대 1만인데, 2,666,799이란 수가 출력되어서 완전탐색으로도 시간내에 풀 수 있겠다고 생각해 완전탐색으로 풀이하였습니다.