[Swift] 백준 문제를 풀면서 겪은 시간초과 유형

#1. 빠른 입출력
먼저, 백준에서 readLine, print 메서드가 다른 언어에서 보다 느리다.
입력은 라이노님이 fread 방식을 swift 버전으로 작성한 코드로 해결할 수 있음.
출력 같은 경우에는 print를 여러번 호출하는 것 보다, string 변수에 저장하고, 한 번에 출력하는 것이 더 빠름

예를 들어,
1
2
3
...
100,000 을 호출한다고 할 때

print(1)
print(2)
print(3)
...
print(100_000)

보다

var str = ""
str += "1\n"
str += "2\n"
str += "3\n"
...
str += "100000\n"
print(str)

이 더 빠르다.

#2. 메서드, 프로퍼티의 시간 복잡도를 알고 풀자.
Swift에서 제공하는 몇몇 메서드들의 시간복잡도는 option + click 으로 시간복잡도를 확인할 수 있음

Int 배열에서 최소값을 찾는 메서드는 min인데, 시간복잡도가 궁금하다. 하면
옵션 클릭하면 다음과 같이 나온다 (Xcode 15)

이런식으로 확인할 수 있음.

최소 10만개의 어레이에서 최소 값의 인덱스를 찾아야 한다면 어떻게 찾을 수 있을까? (시간제한은 1초)
단순하게 다음과 같이 코드를 작성했었음

let n = Int(readLine()!)!
let array = readLine()!.split(separator: " ").map { Int($0)! }
print(array.firstIndex(where: { $0 == array.min()! })!)

시간초과가 발생했다.

왜?

firstIndex 메서드가 $O(n)$ 이고, min 메서드도 $O(n)$이다.
이 코드의 시간복잡도는?
$O(n^2)$다.
$n$이 최대 10만이므로, 10만 * 10만은.. PS에서 1초안에 해결할 수 없다고 볼 수 있다..

해결방법은 진짜 쉽다.

let n = Int(readLine()!)!
let array = readLine()!.split(separator: " ").map { Int($0)! }
let minValue = array.min()!
print(array.firstIndex(where: { $0 == minValue })!)

그냥 minValue 변수 하나가 추가된 것 뿐인데 이것은 통과한다.
왜냐. 이 코드의 시간복잡도는 $O(n)$이기 때문이다.

PS를 하면서 사소한 실수로도 시간초과를 나는 경우를 겪을 수 있으므로, 주의해야 한다고 생각했다.

떠오르는 부분만 작성하고 이 글은 계속해서 보완할 예정...