문제 풀이 아이디어
해당 문제를 풀기 위해서는 빠른 입출력을 구현해야 합니다. Swift에서 빠른 입출력을 구현하기 위해서는 별도의 클래스를 선언하고 사용해야 합니다.
FileIO 클래스는 표준 입력 (= 키보드 입력)을 받아서 byte의 배열로 저장합니다. 그리고 나서 byte를 하나하나 읽어서 원하는 자료형으로 리턴합니다.
FileIO 구현
배경 지식
아래 코드를 이해하기 위해서는 3가지 배경 지식을 이해해야 합니다.
File Descriptor
아래 코드를 보면 FileIO 객체를 만들기 위해서 FileHandle 객체를 사용하고 있습니다. 공식문서를 참고해보면 FileHandle 객체는 파일 (혹은 소켓, 파이프 등 데이터 스트림)에 접근할 수 있도록 해줍니다. FileHandle 객체를 만든다는 것은 특정 파일의 file descriptor를 소유한다는 것을 의미합니다.
file descriptor는 리눅스 (혹은 유닉스) 운영체제에서 프로세스가 특정 파일에 접근할 때 사용하는 추상적인 값입니다. 일종의 포인터라고 생각하면 됩니다. 이는 임의로 정하는 것은 아니고 운영체제에 의해서 관리됩니다.
Standard Input
FileHandle 인스턴스를 만들 때 standartd input에 대한 fileHandle 인스턴스를 만들었습니다. standard input은 표준입력의 의미합니다. (file descriptor 0번) 우리가 짠 코드는 커맨드 라인에서 실행이 되므로 표준 입력이 키보드 입력으로 정해져있습니다. (표준입력은 프로세스 마다 다릅니다.)
키보드 입력을 파일로 간주에서 fileHandle 객체를 만드는 이유는 유닉스 계열의 운영체제에서는 하드웨어를 파일로 추상화해서 관리하기 때문입니다. 키보드의 입력의 하나의 파일로 간주하는 것입니다.
Inline Function
함수가 실행되는 과정은 크게 호출 → 실행의 두 단계를 따릅니다. 컴파일 될 때 실행된 함수는 별도의 공간에 저장이 되고 코드를 실행하는 과정에서 함수가 포함된 코드를 만나면 해당 함수를 “호출"한 이후에만 실행할 수 있습니다. 하지만 실행이 아주 빠른 경우, 호출하는 시간이 상대적으로 오래 걸리게 됩니다. (실행 시간 <<< 호출 시간)
이 경우에 컴파일러에게 해당 함수의 코드를 함수의 자리에 바로 삽입해달라고 요청할 수 있습니다. 즉 다른 공간에 함수를 저장하고 참조하는 대신 함수 내부의 코드 자체를 실행 코드에 넣어버리는 형식입니다.
FileIO 코드
final class FileIO {
private let buffer:[UInt8]
// 입력을 byte의 배열로 바꾸어서 저장
private var index: Int = 0
// 현재 읽어야 할 byte의 위치를 저장
//❓ FileHandle 객체 = 파일 (소켓, 파이프)의 데이터에 접근할 수 있게 해준다.
// FileHandle 객체를 만든다는 것은 특정 file descriptor의 소유권을 가진다는 뜻이다.
// file descriptor: 리눅스 혹은 유닉스 운영체제에서 프로세스가 특정 파일에 접근할 때 사용하는 추상적인 값 (일종의 포인터) -> 운영체제에 의해서 관리된다.
// FileHandle.standardInput은 표준입력에 대한 인스턴스를 만든 것
// 이 코드는 command-line에서 실행되므로 표준입력이 키보드입력으로 정해져있다. (프로세스 마다 표준은 다름)
// 키보드 입력이 파일인 이유는 유닉스 계열의 운영체제에서 하드웨어를 파일로 추상화해서 사용하기 때문
init(fileHandle: FileHandle = FileHandle.standardInput) {
self.buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)]
// 현재 파일(= 커맨드 라인 입력)을 끝까지 한방에 읽어와서 buffer에 저장한다.
//⭐️ 마지막에 0을 추가해서 buffer의 끝 부분임을 알림
}
//❓ 인라인 함수
// 함수를 사용할 때는 호출 -> 실행의 두 가지 단계를 따르는데 (함수는 메모리에 다른 곳에 저장했다가 호출함)
// 실행이 아주 빠른 함수의 경우 호출에 걸리는 시간이 오히려 오래 걸릴 수 있다.
// 따라서 컴파일을 할 때 함수의 코드를 바로 호출할 자리에 삽입한다. (호출 필요 없이 바로 실행)
//✅ 1 btye를 읽어오는 함수
@inline(__always) private func read() -> UInt8 {
defer { index += 1 } //👉 읽고 나서 index 추가
return buffer[index]
}
//✅ 연속된 byte값 Int로 변환해서 읽어오는 함수
@inline(__always) func readInt() -> Int {
var sum = 0 //👉 결과를 저장할 곳
var now = read() //👉 지금 index의 byte 값
var isPositive = true //👉 부호를 저장할 곳
while now == 10
|| now == 32 { now = read() } //👉 공백과 줄바꿈 무시 (다음 byte 읽기)
if now == 45 { isPositive.toggle(); now = read() } // "-"가 나오면 음수 처리
//⭐️ 0 ~ 9에 해당하는 byte값일때만
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48) //👉 현재까지의 합 * 10하고 다음 숫자 더하기 (자릿수 적용)
now = read() //👉 다음 byte 읽기
}
return sum * (isPositive ? 1:-1) //👉 부호까지 계산해서 반환하기
}
//✅ String으로 일어오는 함수
@inline(__always) func readString() -> String {
var now = read()
while now == 10 || now == 32 { now = read() } //👉 공백과 줄바꿈 무시 (다음 byte 읽기)
//⭐️ 공백이나 줄바꿈이 아니라면 그 index를 기록 (문자열의 시작점)
// -1을 해주는 이유는 index 값은 앞으로 읽을 다음 byte를 가리키고 있으므로.
let beginIndex = index-1
//⭐️ 공백(32) 혹은 줄바꿈(10) 혹은 파일의 끝(0)이 나오기 전까지 read
while now != 10,
now != 32,
now != 0 { now = read() }
//⭐️ 공백(32) 혹은 줄바꿈(10) 혹은 파일의 끝(0)이 나와서 while문을 벗어나면
// 시작 index부터 문자열의 index까지 Array를 잘라서 String으로 타입 변환해서 리턴
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
//✅ 연속된 byte값 읽어오기
@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)])
}
}문제 풀이
FileIO를 구현했다면 문제 풀이 과정 자체는 심플합니다. 위에 구현한 readInt()를 활용해서 숫자를 읽습니다.
let fileIO = FileIO()
let T = fileIO.readInt()
for _ in 0..<T {
//⭐️ 1줄을 통으로 읽어오는 것이 아니므로 A, B 각각 1번씩 실행
let A = fileIO.readInt()
let B = fileIO.readInt()
print(A + B)
}🤔 고민해볼 문제들
Data 자체를 이용하는 FileIO 클래스
Swift의 Data 클래스 자체도 RandomAccessCollection 프로토콜을 준수하는 클래스입니다. 따라서 아래 처럼 Data 자체의 index를 가지고 FileIO를 구현할 수도 있을 것입니다.
final class FileIO {
private let buffer: Data
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
self.buffer = try! fileHandle.readToEnd()!
}
// ... 후략 ...
}🚫 하지만 아직 원인을 파악하지 못했지만 위처럼 byte 들의 Array를 이용하는 방식보다 속도가 느립니다. 게다가 이번 문제를 풀 때 어쩔 때는 가까스로 통과하지만 대부분의 경우 시간초과가 나는 모습을 볼 수 있었습니다.
readLine() 처럼 한 줄을 통으로 읽어오면?
기존의 입력을 받기 위한 코드인 readLine() 처럼 한줄을 통째로 읽어오는 코드를 작성할 수는 없을까요? 물론 가능합니다. 아래의 함수처럼 줄 바꿈만 무시해서 읽는다면 충분히 가능한 함수입니다.
@inline(__always) func readline() -> String {
var str = ""
var now = read()
while now == 10 { now = read() } //👉 줄바꿈만 무시
while now != 10 && now != 0 {
str += String(bytes: [now], encoding: .ascii)!
now = read()
}
return str
}🚫 하지만 이 코드의 문제는 여기서 발생하는 것이 아닙니다. 바로 A와 B를 split하는 과정에서 발생합니다. split은 시간 복잡도가 O(n)으로 (n의 collection의 길이) 리소스를 많이 잡아먹는 메소드입니다. 왠만하면 반복문에 사용하지 않는 것이 좋습니다. 실제로 아래 코드를 채점해본 결과 시간초과가 발생하였습니다.
for _ in 0..<T {
let input = fileIO.readline().split(separator: " ").map { Int(String($0))! }
print(input[0] + input[1])
}참고한 블로그🙏
FileIO 코드
[Swift] 빠른 입출력(fread) - FileIO
File Descriptor
파일 디스크립터(File Descriptor) 란 무엇인가?
Standard Input
Inline Function
