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

시간초과 너무 싫어 ㅜㅜ

개요

저번에 쓴 글에서는 라이노님의 파일입출력을 사용해서 시간초과를 해결하는 방식을 설명했다.

지금까지 몇 문제를 더 풀어보면서 라이노님의 파일입출력을 써야하는 상황은 보통 입/출력이 3,000,000 이다(아마 백만부터는 그냥 사용하면 된다고 생각하면 될듯).
이 정도 입출력에서는 Swift에서 제공하는 readLine() 을 사용하면 시간초과가 나는 것을 알았다.

파일입출력 문제

하지만 이 파일입출력 조차도 통과하지 못한 문제를 발견했으니..

이 문제를 풀면서 비트마스크에 대한 개념을 공부했는데 정작 어렵게 푼 문제를 돌리려다보니까 시간초과가 나서 라이노님의 파일입출력을 사용했는데도 시간초과가 났다.

혹시나 비트마스크를 잘못계산해서 시간초과가 나는건지 궁금하기도 했는데 아무리봐도 파일입출력 문제가 아닌이상 코드 중에 O(1) 이 넘어가는게 없어보였기 때문이다.

그래서 맞은사람이 있을까 했는데 요즘 자주보이는 Wapas 분이 문제를 맞은 것을 알아챘다. 결국 이분의 코드를 보기위해서 C++로 정답을 복붙해서 맞춘다음에 열람을 하게 되었다.(감사합니다 Wapas)

일단 이 분의 파일입출력은 다음과 같다.

import Foundation
//원래는 Class 처리가 없으셨지만 내가 임시로 구현했다.
class FileIO {
    @inline(__always) private var buffer: [UInt8] = Array(FileHandle.standardInput.readDataToEndOfFile()) + [0], byteIdx = 0
    
    @inline(__always) private func readByte() -> UInt8 {
        defer { byteIdx += 1 }
        return buffer.withUnsafeBufferPointer { $0[byteIdx] }
    }
    
    @inline(__always) func readInt() -> Int {
        var number = 0, byte = readByte(), isNegative = false
        while byte == 10 || byte == 32 { byte = readByte() }
        if byte == 45 { byte = readByte(); isNegative = true }
        while 48...57 ~= byte { number = number * 10 + Int(byte - 48); byte = readByte() }
        return number * (isNegative ? -1 : 1)
    }
    
    @inline(__always) func readStirngSum() -> Int {
        var byte = readByte()
        while byte == 10 || byte == 32 { byte = readByte() }
        var sum = Int(byte)
        while byte != 10 && byte != 32 && byte != 0 { byte = readByte(); sum += Int(byte) }
        return sum - Int(byte)
    }
    
    @inline(__always) private func write(_ output: String) {
        FileHandle.standardOutput.write(output.data(using: .utf8)!)
    }
}

전혀 이해가 안되는 코드다. 이 코드를 언젠가는 라이노님것과 비교하면서 봐야겠지만 이 코드를 사용하면 이 문제를 풀 수 있다.

하지만 귀찮은 작업이 있었으니... 그것은 String값은 내가 직접 int로 바꾸어서 넣어줘야 하는 것이다.

정확한 원리는 아직 모르지만 아마 String값을 그대로 받으면 거기서 시간초과가 나서 Byte로 변환해서 시간을 단축시키는 것 이겠지만 그러기 위해서는 내가 해당 String값을 Byte로 변환한 값을 코드에 적용시켜줘야 하는 것이다.

보통 입력값을 받아 switch-case 구문을 사용할 때는 다음과 같다.

switch fileIO.readStirngSum() {
    case "add": {
    	//do someting
    }
    default: {
    break
 }

하지만 Byte로 switch-case를 사용해야 하기 때문에 일일히 해당 문자열을 Byte로 바꾸어서 case구문에 넣어줘야 한다.

switch fileIO.readStirngSum() {
    case 297: { // "add" 문자열을 바이트 변환시 값.
    	//do someting
    }
    default: {
    break
 }

이런 번거로움을 감수해야만 이 문제를 해결 할 수 있다.

결론

라이노님과 Wapas 님의 코드가 없었다면 Swift로는 절대 못푸는 문제가 아직까지 많은 것 같다. 어떻게라도 감사한 마음을 표현하고 싶은데 전혀 친분이나 안면이 없어서 말할 기회가 없어서 아쉽다.
백준 문제들을 공부하면서 해당 개념에 대한 알고리즘을 공부하고 싶은데 이런 상황이 발생할 때마다 참 아쉽다. 나 포함해서 다른 Swift로 문제를 푸는 분들이 특정 문제에서 시간초과로 많이들 포기하시는데 이 파일입출력이 도움이 되었으면 한다. 사실 내가 한것은 아무것도 없고 두 분의 노력에 다시한번 감사를 전한다.