[Algorithm/BOJ] 18258 - 큐2 Swift Python

문제 풀이: 

스위프트에서 큐를 지원해주지 않아 직접 구현해야 합니다.

하지만 배열 하나로 구현했을 때 시간상 효율이 좋지 않아 두개의 배열(스택)을 이용해서 큐를 구현했습니다.

그래도 시간초과가 나므로 라이노님의 빠른 입력 클래스를 사용했습니다. 

또한, push, pop, empty, size, front, back에 해당하는 아스키 코드를 미리 구해 넣어 시간을 줄였습니다. 

 

파이썬은 collections의 deque를 사용해서 쉽게 풀 수 있었습니다.

코드: 

Swift

import Foundation

// 라이노님 빠른 입력 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }
        
        return buffer.withUnsafeBufferPointer { $0[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() } // 공백과 줄바꿈 무시
        
        while now != 10
                && now != 32 && now != 0 {
            str += Int(now)
            now = read()
        }
        
        return str
    }
}

// 2개의 스택(배열)을 이용한 큐 구현
struct Queue {
    var left = [Int]()
    var right = [Int]()
    
    var count: Int {
        left.count + right.count
    }
    
    var isEmpty: Bool {
        left.isEmpty && right.isEmpty
    }
    
    var first: Int? {
        guard !isEmpty else { return -1 }
        return right.isEmpty ? left.first : right.last
    }
    
    var last: Int? {
        guard !isEmpty else { return -1 }
        return left.isEmpty ? right.first : left.last
    }
    
    mutating func enqueue(_ value: Int) {
        left.append(value)
    }
    
    mutating func dequeue() -> Int? {
        guard !isEmpty else { return -1 }
        
        if right.isEmpty {
            right = left.reversed()
            left.removeAll()
        }
        return right.popLast()
    }
}

let file = FileIO()
var q = Queue()
var res = ""

for _ in 0 ..< file.readInt() {
    // 아스키 코드로 입력 받아서 Int형으로 캐스팅하는 시간을 줄임
    let cmd = file.readString()
    // push
    if cmd == 448 {
        q.enqueue(file.readInt())
    }
    // pop
    else if cmd == 335 {
        res += q.isEmpty ? "-1\n" : "\(q.dequeue()!)\n"
    }
    // size
    else if cmd == 443 {
        res += "\(q.count)\n"
    }
    // empty
    else if cmd == 559 {
        res += q.isEmpty ? "1\n" : "0\n"
    }
    // front
    else if cmd == 553 {
        res += "\(q.first!)\n"
    }
    // back
    else if cmd == 401 {
        res += "\(q.last!)\n"
    }
}
print(res)

 

Python

import sys
from collections import deque

q = deque([])
for i in range(1, int(sys.stdin.readline())+1):
    q.append(i)

while len(q) > 1:
    q.popleft()
    q.append(q.popleft())
print(q.popleft())

 

문제: 

18258번: 큐 2