[Swift] Queue 만들기 (BOJ 18258) && discardableResult란? && reverse()와 reversed()차이

18258 - 큐 2

단, 이 문제에서 연산 당 시간 복잡도가 O(1)이어야 한다는 점에 유의해야한다.

흔히 하는 큐를 구현하면 될 것 같지만 Swift에서는 다른 언어에
비해서 까다롭다.
Swift에서의 문제는 2가지인데

---

1.Swift는 표준입출력이 느리다.
2.Array의 removeFirst()의 시간복잡도는 O(N)이다.

---

1번 문제의 해결책

1번 문제는 표준 입출력을 다른 방법으로 구현해야한다.

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() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @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)])
    }
}

출처=https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88#file-usage-swift

---

2번 문제의 해결책 1

import Foundation

struct queue<T>{
  private var elements:[T?] = [] // 배열에 nil을 설정할 수 있기 때문에 T에서 T?로 자료형을 변경한다.
  private var head:Int = 0 
  
  var isEmpty : Bool {
    return count == 0
  }

  var count: Int {
   return elements.count - front
  }
  
  mutating func enqueue(_ element:T){
    elements.append(element)
  }
  
  mutating func dequeue() -> T? {
        guard let element = queue[head] else { return nil }
    
        queue[head] = nil
        head += 1
        
        let percentage = Double(head) / Double(queue.count)
        if queue.count > 50, percentage > 0.25 { // 배열의 비어있는 요소가 많아질 경우 비어있는 부분을 제거해주는 작업을 한다.
            queue.removeFirst(head)
            front = 0
        }
        
        return element
    }
}

Dequeue

Dequeue할 시 queue[head]를 nil로 바꾸고 head += 1


만약 nil이 일정 이상 차면 queue.removeFirst(head)로
head 개수만큼 제거

---

2번 문제의 해결책 2 - 더블 스택사용

struct QueueStack<T> {
  private var dequeueStack: [T] = []
  private var enqueueStack: [T] = []
  
  var isEmpty: Bool {
    return dequeueStack.isEmpty && enqueueStack.isEmpty
  }
  var peek: T? {
    return !dequeueStack.isEmpty ? dequeueStack.last : enqueueStack.first
  }
  
  mutating func enqueue(_ element: T) {
    enqueueStack.append(element)
  }
  
  @discardableResult
  mutating func dequeue() -> T? {
    if dequeueStack.isEmpty {
      dequeueStack = enqueueStack.reversed()
      enqueueStack.removeAll()
    }
    return dequeueStack.popLast()
  }
}

++(@discardableResult 는 " 내가 return을 쓰든 안쓰든 신경 안 써도 돼. warning 띄워주지 마! "라는 용도로 쓰인다)

단순히 이해를 돕자면 dequeue 스택은 dequeue할 때만 사용하고 enqueue 스택은 enqueue할 때만 사용한다.
또한 ”reversed()는 공간을 역순으로 돌리기에 시간 복잡도가 n이 될 수도 있는 것 아닌가?“고 생각할 수 있다.
하지만, 그것은 reverse()이다. reverse() = O(n)
reversed()는 element를 역순으로 나타내는 뷰를 반환해준다.
그래서 시간복잡도는 1이다. reversed() = O(1)