시간 초과

Swift 문법에 익숙해지기 위해 Swift 를 이용해 문제를 풀고 있는데, 시간 초과가 정말 많이 납니다. 오름차순으로 수를 정렬해 출력하는 수 정렬하기 3 문제에서 swift 가 제공하는 sort 함수를 이용해 문제를 풀면 어김 없이 시간 초과가 납니다.

import Foundation

let N = Int(readLine()!)!
var arr = [Int](repeating: 0, count: N)

for i in 0...N-1 {
    arr[i] = Int(readLine()!)!
}
arr.sort()

for i in 0...N-1 {
    print(arr[i])
}

알고리즘

그러면 시간복잡도가 O(n+k) 인 counting sort 를 이용해 문제를 풀면 어떨까요?

counting sort 란?

Link : 애니메이션
숫자에 해당하는 인덱스를 가지는 counting array 를 만들어놓고, 배열의 값에는 숫자가 등장하는 빈도수를 저장해놓습니다.
counting array 에 대해 직전 요소들의 값을 더해준 뒤, 입력 배열과 동일한 크기의 출력 배열을 만들어 입력 배열의 역순으로 출력 배열을 채워 줍니다.

counting sort 또한 시간 초과가 납니다. 코드는 아래와 같습니다.

import Foundation

let N = Int(readLine()!)!
var arr = [Int](repeating: 0, count: 10001)
var result = ""

for _ in 0..<N {
    let n = Int(readLine()!)!
    arr[n] += 1
}

for i in 1...10000 where arr[i] > 0 {
    for _ in 0..<arr[i] {
        print(i)
    }
}

Swift 시간 초과 줄이기 : 입출력

Swift 는 입출력이 상당히 느린 편이고, 백준에서도 Swift 에 대한 추가 시간을 주지 않는다고 합니다. 따라서 입출력 속도를 향상시키기 위한 방안을 활용해야 시간 초과 문제를 해결할 수 있습니다.
Swift 문제 풀이에 최적화된 입력 유틸리티 클래스를 사용하면 시간 초과 문제가 해결됩니다.

Link : Swift 입력 유틸리티 클래스

import Foundation

final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
            || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45{ isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
            || now == 32 { now = read() } // 공백과 줄바꿈 무시

        while now != 10
            && now != 32 && now != 0 {
                str += String(bytes: [now], encoding: .ascii)!
                now = read()
        }

        return str
    }
}

let file = FileIO()

let N = file.readInt()
var arr = [Int](repeating: 0, count: 10001)


for _ in 0..<N {
    let n = file.readInt()
    arr[n] += 1
}

var answer = ""
for i in 1...10000 {
    answer += String(repeating:"\(i)\n",count:arr[i])
}
print(answer)

참고

• counting sort : https://soobarkbar.tistory.com/101