[Swift] 백준 18258번 - 큐 2

백준 문제 모음

문제 링크

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

18258번: 큐 2

 

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야 하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

입출력 예시

알고리즘 분류

• 자료 구조
• 큐

---

소스 코드

var queue = [Int]()
var firstIndex = 0

for _ in 0..<Int(readLine()!)! {
    let input = readLine()!.split(separator: " ").map{String($0)}
    
    switch input[0] {
    case "push":
        queue.append(Int(input[1])!)
    case "pop":
        if queue.count-firstIndex == 0{
            print(-1)
        }else{
            print(queue[firstIndex])
            firstIndex += 1
        }
    case "size":
        print(queue.count - firstIndex)
    case "empty":
        print(queue.count-firstIndex == 0 ? 1 : 0)
    case "front":
        print(queue.count-firstIndex == 0 ? -1 : queue[firstIndex])
    case "back":
        print(queue.count-firstIndex == 0 ? -1 : queue.last!)
    default:
        break
    }
}

• 시간초과 코드
• switch문을 사용하여 각 명령에 대한 동작 구현 

문제 풀이

• 라이노님 빠른 입력 FileIO 사용
  • 기본 readLine() 메서드보다 빠르게 동작
  • FileIO에 대한 설명
  • https://m.blog.naver.com/gustn3964/222258493870

라이노님의 빠른 입력 readLine 분석하기!

• 구조체로 큐(queue)를 구현한다.
  • pop에서 remove는 시간이 오래 걸리기 때문에 시작 인덱스를 나타내는 변수 start를 1 증가시켜 다음 요소를 가리키도록 한다.
  • mutating
    
    • 특정 메서드 내에서 구조체 또는 열거형의 프로퍼티를 수정해야 하는 경우, 해당 메서드의 동작을 변경하도록 하는 것
• main 함수에 동작들을 구현한다.
  • FileIO를 사용하여 입력받는다.
  • if문을 사용하여 각 명령에 대한 동작을 수행하고 결과를 output에 추가한다.
  • output변수를 출력한다.

정답 코드

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

func stringToAscii(_ str: String) -> Int {
    str.map { $0.asciiValue! }.map { Int($0) }.reduce(0) {$0 + $1}
}

let FRONT = stringToAscii("front")
let EMPTY = stringToAscii("empty")
let BACK = stringToAscii("back")
let SIZE = stringToAscii("size")
let POP = stringToAscii("pop")

struct Queue {
    private var nums = [Int]()
    private var start = 0
    private var end = 0
    
    var empty: Bool{
        start == end
    }
    var size: Int {
        end - start
    }
    mutating func pop() -> Int {
        if empty {
            return -1
        }
        let num = nums[start]
        start += 1
        return num
    }
    var front: Int {
        if empty {
            return -1
        }
        return nums[start]
    }
    var back: Int {
        if empty {
            return -1
        }
        return nums[end-1]
    }
    mutating func push(_ num: Int) {
        nums.append(num)
        end += 1
    }
}

func main() {
    let file = FileIO()
    let numCommands = file.readInt()
    
    var queue = Queue()
    var output = ""
    
    for _ in 1...numCommands {
        let line = file.readString()
        
        
        if line == FRONT {
            output += "\(queue.front)\n"
        } else if line == EMPTY {
            output += queue.empty ? "1\n" : "0\n"
            
        } else if line == BACK {
            output += "\(queue.back)\n"
            
        } else if line == SIZE {
            output += "\(queue.size)\n"
            
        } else if line == POP {
            output += "\(queue.pop())\n"
        } else {
            let value = file.readInt()
            queue.push( value)
        }
    }
    print(output)
}

main()

• 400ms 소요