FileIO.swift (+ Swift의 문자열 처리 방식)

Swift로 백준 문제를 풀었는데, 로직의 시간 복잡도에는 문제가 없어 보이는데도 시간 초과 판정을 받았다.
Python에서 정상적으로 동작한 코드를 그대로 Swift로 옮긴건데도...

이는 Swift와 Python의 문자열 처리 방식 차이 때문이라고 한다.

Swift와 Python의 문자열 처리 방식 차이

• Python: O(1) 인덱싱

Python 문자열은 내부적으로 고정된 인코딩 방식을 사용하여 각 문자를 저장한다. 문자열이 생성될 때 인코딩 방식이 결정되면(ASCII, Latin-1, UCS-2, UCS-4 중 하나), 각 문자의 위치를 수학적으로 바로 계산할 수 있다. 따라서 인덱스로 접근(s[0]), 슬라이싱(s[1:3]) 등이 O(1) 상수 시간에 이루어진다.

s = "안녕하세요Hello"
print(s[0])      # O(1) - 즉시 접근
print(s[5])      # O(1) - 즉시 접근
print(s[3:7])    # O(k) - k는 슬라이스 길이

• Swift: O(n) 인덱싱

Swift의 String은 Unicode를 완벽하게 지원하기 위해 Extended Grapheme Cluster 단위로 문자를 처리한다. 이는 사용자가 인식하는 "하나의 문자"를 정확히 표현하기 위함인데, 문제는 각 문자의 바이트 크기가 가변적이라는 것이다. 예를 들어 "👨‍👩‍👧‍👦"는 하나의 문자로 인식되지만 실제로는 여러 개의 Unicode scalar로 구성되어 있다.
따라서 n번째 문자를 찾으려면 문자열의 처음부터 순차적으로 세어나가야 하므로 시간복잡도가 O(n)이 된다.

let s = "안녕하세요Hello"
// n번째 문자 접근 - O(n)
let index = s.index(s.startIndex, offsetBy: 5)
let char = s[index]

// 인덱스 직접 접근 불가
// let char = s[5]  // ❌ 컴파일 에러!

실제로 위 이모지를 나누면 이렇게 보인다.

따라서 Swift에서 문자열로 처리하지 않고 숫자로 처리할 수 있는 문제는 최대한 숫자로 처리하도록 생각해보도록 하자.

---

FileIO.swift 코드

무튼 이런 문제를 해결하기 위해 라이노님이 c의 fread 메서드를 swift로 옮겨놓은 코드를 공유해주셨는데,
두고두고 써먹으려고 가져왔다.

출처: 라이노님의 gist

🔖 참고: C의 fread 메서드
fread는 C 언어 표준 라이브러리의 함수로, 파일이나 표준 입력(stdin)의 데이터를 빠르게 대량으로 읽어오기 위한 함수이다.

파이썬으로도 sys.stdin 으로 파일째로 한꺼번에 읽어서 풀어본 적이 있는데 그런 느낌인 것 같다.

import Foundation


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

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

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

        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 now = read()

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

        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

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

        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}

참고: 바이트 단위 연산
위 코드는 숫자와 문자를 바이트 단위로 처리하는데,
이는 문자를 한 글자씩 쪼개서 숫자로 저장한 후, 필요할 때 다시 문자로 변환하는 방식이다.

이 과정에서 숫자와 문자는 UInt8 형식의 ASCII 코드로 변환되어 처리되는데,
이렇게 하면 메모리를 절약하고 처리 속도를 높일 수 있다.
단, 문자와 숫자를 변환하는 과정을 직접 구현해야 한다는 단점이 있음!

---

코드 흐름

1. 입력을 한꺼번에 읽고** UInt8 배열(buffer)에 저장
2. read()로 바이트 단위로 하나씩 읽어옴
3. 공백/줄바꿈을 무시하고 필요한 데이터만 추출
4. ASCII 변환을 통해 정수 또는 문자열 변환
5. 최적화된 입력 방식으로 빠르게 사용 가능!