문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
내가 푼 풀이
- 큐 구현자체는 어렵지않다. 해당 명령어만 메소드와 속성으로 만든 구조체 하나 만들면된다.
- 문제는 엄청 많은 입력값과 그에 준하는 출력이다.
- swift에 내장된 readLine() 과 print는 너무 느려서 시간초과가 난다.
- 이 문제는 Swift 파일 입출력, 큐의 index를 이용한 pop, 입력된 명령어를 byte로 바꿔 풀어야 겨우 시간초과를 면할 수 있었다.
- 추가로 출력은 문자열출력이 print 보다 더 빠르다
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() -> Int {
var str = 0
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 {
str += Int(now)
now = read()
}
return str
}
@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)])
}
}
struct Queue {
var elements = [Int]()
var idx = 0
var count: Int {
return elements.count - idx
}
var front: Int {
if elements.isEmpty || idx >= elements.count {
return -1
} else {
return elements[idx]
}
}
var back: Int {
if elements.isEmpty || idx >= elements.count {
return -1
} else {
return elements[elements.count - 1]
}
}
var isEmpty: Int {
if elements.isEmpty || idx >= elements.count {
return 1
} else {
return 0
}
}
mutating func push(element: Int) {
elements.append(element)
}
mutating func pop() -> Int {
if elements.isEmpty || idx >= elements.count {
return -1
} else {
let output = elements[idx]
idx += 1
return output
}
}
}
let fIO = FileIO()
let N = fIO.readInt()
var queue = Queue()
var answer = ""
for i in 0..<N {
let operation = fIO.readString()
switch operation {
case 448:
//push
queue.push(element: fIO.readInt())
case 335:
//pop
answer += "\(queue.pop())\n"
case 443:
//size
answer += "\(queue.count)\n"
case 559:
//empty
answer += "\(queue.isEmpty)\n"
case 553:
//front
answer += "\(queue.front)\n"
case 401:
//back
answer += "\(queue.back)\n"
default:
continue
}
}
print(answer)'코딩테스트 > 백준' 카테고리의 다른 글
| BOJ-2346 풍선 터트리기 Swift (0) | 2024.04.03 |
|---|---|
| BOJ-2164 카드2 Swift (0) | 2024.04.02 |
| BOJ-9012 괄호 Swift (0) | 2024.04.02 |
| BOJ-10773 제로 Swift (1) | 2024.04.02 |
| BOJ-28278 스택 2 Swift (0) | 2024.04.02 |