백준은 Swift 시간초과에 관대해줘라

극악의 시간초과 ☹️

코딩테스트를 준비하면서 한번씩 백준에서 이런 현상이 있었다.

그것은 시간초과

단순히 알고리즘이 잘못된 시간초과가 아닌 문제에 필요한 알고리즘을 사용했음에도 생기는 현상이다.

Swift는 아직 다른 언어에 비해 역사도 짧고(처음나온게 2014년이라고 한다. c++는 1985.. 한참 형님이다.) 코테에서 주로 쓰이는 언어가 아닌지라 이 언어로 코테를 칠 때 한번씩 이런 현상이 있다.

몇 문제들
빠른 A+B
수 정렬하기

예전에는 이런 문제들을 보면서 도저히 틀렸다고 생각이 안되어서 스트레스가 이만저만 아니었다.

결국 찾다가 두 가지의 방법을 알게 되었다.

1.입력값

우연히 알게 된 라이노님(이 분으로 추정된다)의 FileIO Class를 도입했다.

import Foundation

final class FileIO {
    private let buffer: Data
    private var index: Int = 0
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        self.buffer = try! fileHandle.readToEnd()! // 인덱스 범위 넘어가는 것 방지
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer {
            index += 1
        }
        guard index < buffer.count else { return 0 }
        
        return buffer[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
        }
  }

이 클래스를 이용하면 파일입출력을 이용해서 Int(readLine()!)! 함수를 대체하여 FileIO.readInt() 로 입력값을 받아 사용할 수 있다.

Xcode에서는 입력받은 후 print() 문을 써도 자동으로는 안보인다. EOF방식이라서 리눅스 명령어를 써야하는데 ctrl+d를 커맨드창에서 사용하면 지금까지 입력한 입력값을 종료하고 print() 함수가 실행된다. (처음에는 확인이 안돼서 어리둥절했다.)

2. 출력값

생각보다 print()가 시간초과에 주범이 된다. 특히 여러개의 출력을 해야하는 경우가 그런데 이 때는 다음과 같은 방법으로 대처가 가능하다.

var result = ""
var resultArr = [Int]()
func foo(num: Int) -> Int{
  //특정함수
}

for i in 0..<1000000 {
	resultArr.append(foo(num: i)) //일반적인 방법
	result.write(String(foo(num: i)) + "\n") //write 이용방법
}

//1. 일반적인 출력
for i in 0..<resultArr.count {
	print(resultArr[i])
}

//2. string 출력
print(result)

위의 코드는 비교를 위해 간단하게 만든 것인데 중요한 점은 그 때 마다의 결과값을 String화 하여(대게 Int결과값이 많다.) string 변수에 write를 하는 것이다. 변수에 += 보다 write()를 사용했을 때 시간을 줄일 수 있다. 이 점도 파일입출력에 관련된 것 같다.

결론

Swift 입출력을 빠르게 하려면 파일입출력을 사용해라!!

Swift의 입출력은 코딩테스트에서는 상당히 느린편에 속한 것 같다. 물론 실제 기업 코테에서는 어느정도 시간초과에 대해 준비하고 내서 알고리즘이 정확한데 시간초과 날 일은 없다고 생각하지만, 백준에서 코테를 공부하면서 맞는 알고리즘인데 불구하고 시간초과가 나는 현상 때문에 스트레스 받지 않았으면 하는 바람에 적게 되었다.

요즘에는 시간초과가 계속 나면 Swift로 맞은사람을 체크하는데 예상외로 너무 적으면 파일입출력으로 변형해서 풀어본다. 특히 문제 난이도가 낮을 때 이런경우면 거의 이 문제인 것 같다.