[Swift] 백준 - 큐 2

https://www.acmicpc.net/problem/18258

 

BFS를 활용할때 Array.removeFirst를 사용해 큐처럼 사용해도 시간초과가 되지 않길래.

 

따로 큐를 구현하지 않아도 괜찮은가? 생각이 들어 문제를 풀어보았다.

 

 

switch문으로 간단하게 구현해보았다.

 

import Foundation

func main() {
   
    let N = Int(readLine()!)!
    
    
    var queue : [Int] = []
    
    for _ in 0..<N {
        let enter = readLine()!.split(separator: " ")
        
        switch enter[0]{
        case "push":
            if let value = Int(enter[1]){
                queue.append(value)
            }
        case "front":
            if queue.isEmpty{
                print(-1)
            }else{
                print(Int(queue.first!))
            }
        case "pop":
            if queue.isEmpty{
                print(-1)
            }else{
                print(queue.removeFirst())
            }
        case "size":
            print(queue.count)
        case "empty":
            if queue.isEmpty{
                print(1)
            }else{
                print(0)
            }
        case "back":
            if queue.isEmpty{
                print(-1)
            }else{
                print(Int(queue.last!))
            }
            
        default:
            return
        }
    }
    
}

// main 함수 실행
main()

 

그런데 시간초과가 발생했다.

 

역시 타 언어의 큐가 되지 않는다. 

 

인덱스를 바꿔주는 방식으로 만들어보자

import Foundation

struct Queue {
    private var elements: [Int] = []
    private var frontIndex: Int = 0

    mutating func push(_ value: Int) {
        elements.append(value)
    }

    mutating func pop() -> Int? {
        guard frontIndex < elements.count else { return nil }
        let value = elements[frontIndex]
        frontIndex += 1
        return value
    }

    func front() -> Int? {
        guard frontIndex < elements.count else { return nil }
        return elements[frontIndex]
    }

    func back() -> Int? {
        guard frontIndex < elements.count else { return nil }
        return elements.last
    }

    func size() -> Int {
        return elements.count - frontIndex
    }

    func empty() -> Int {
        return frontIndex >= elements.count ? 1 : 0
    }
}

let N = Int(readLine()!)!
var queue = Queue()

for _ in 0..<N {
    let enter = readLine()!.split(separator: " ")
    
    switch enter[0] {
    case "push":
        if let value = Int(enter[1]) {
            queue.push(value)
        }
    case "front":
        if let frontValue = queue.front() {
            print(frontValue)
        } else {
            print(-1)
        }
    case "pop":
        if let poppedValue = queue.pop() {
            print(poppedValue)
        } else {
            print(-1)
        }
    case "size":
        print(queue.size())
    case "empty":
        print(queue.empty())
    case "back":
        if let backValue = queue.back() {
            print(backValue)
        } else {
            print(-1)
        }
    default:
        break
    }
}

 

 

엥 그래도 시간초과가 난다.

 

다른 사람들의 코드를 살펴보았다.

 

import Foundation

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
    }
}

struct Queue {
    private var array: [Int] = []
    private var index: Int = 0
    
    var size: Int {
        return array.count - index
    }
    
    var front: Int {
        return self.isEmpty ? -1 : array[index]
    }
    
    var back: Int {
        return self.isEmpty ? -1 : array.last!
    }
    
    var empty: Int {
        return self.isEmpty ? 1 : 0
    }
    
    var isEmpty: Bool {
        return array.count - index <= 0
    }
    
    mutating func push(_ element: Int) {
        array.append(element)
    }
    
    mutating func pop() -> Int {
        guard !self.isEmpty else {
            return -1
        }
        let element = array[index]
        index += 1
        return element
    }
}

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

for _ in 0..<file.readInt() {
    let command = file.readString()
    
    switch command {
    case 448:
        q.push(file.readInt())
    case 335:
        answer += "\(q.pop())\n"
    case 443:
        answer += "\(q.size)\n"
    case 559:
        answer += "\(q.empty)\n"
    case 553:
        answer += "\(q.front)\n"
    case 401:
        answer += "\(q.back)\n"
    default:
        continue
    }
}

print(answer)

 

보면 안되는걸 본거같다.