[Swift/자료구조] 2. 큐(Queue) + 간단한 문제풀이(프로세스)

안녕하세요

이번시간에는 자료구조 큐에 대해 알아보도록 하겠습니다.

 

---

 

큐(Queue) ?

큐는 스택과 마찬가지로 데이터를 저장하고 꺼낼 수 있는 자료구조 입니다.

다만 스택과는 다르게 다른 특징들이 있습니다.

 

큐의 특징(용어)

• First-In-First-Out (FIFO) 구조: 가장먼저 추가된 요소가 가장 먼저 제거됨 (일종의 대기열)
• Enqueue, Dequeue: 요소를 추가, 제거 하는 작업
• Front(peek), Rear (Head, Tail): 맨 앞의 요소, 맨 뒤의 요소

큐의 구현

struct Queue<T> {
    private var queue: [T] = []
    
    var count: Int {
        return queue.count
    }
    
    var isEmpty: Bool {
        return queue.isEmpty
    }
    
    mutating func enqueue(_ element: T) {
        queue.append(element)
    }
    
    mutating func dequeue() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
   
}

 

스택과 마찬가지로 배열을 이용해서 쉽게 구현할 수 있다.

 

다만, 스택과는 다르게 dequeue의 시간복잡도가 O(n)이다.

(맨 앞 요소가 삭제되면, 요소들은 한칸씩 당겨야하기 때문에)

(반대로, 스택은 마지막 요소만 삭제하기 때문에 배열의 요소들이 움직일 필요가 없어서 O(1)의 시간복잡도를 가진다)

 

시간복잡도를 줄이기위해 연결리스트를 이용한 방법도 있다.

관심이 있는 분들은 아래 링크를 참고하면 좋을것 같다.

 

일단 큐가 필요할 때는 위처럼 구현하고, dequeue의 시간복잡도를 줄여야 할 때 다시 찾아보면 될 것 같다.

 

https://nitinagam.medium.com/data-structure-in-swift-queue-part-5-985601071606

Data Structure in Swift (Queue) — Part 5

 

간단한 문제풀이

 

생각 흐름

1. 큐에서 디큐

1-1) 더 큰게 있다면 큐에 다시 추가

1-2) 더 작은게 없다면 큐에서 삭제

 

2. location 처리는 어떻게 ?

2-1) 결국 location 요소가 몇 번째로 실행되는지를 출력하는 문제인데 큐의 요소가 바뀌면 인덱싱도 자연히 바뀐다..

2-2) 예를들어, location이 2일 때는 인덱스2의 요소를 추적해서 실행이 됐을 때 큐에 남은 요소갯수를 파악하면 됨 

 

func solution(_ priorities:[Int], _ location:Int) -> Int {

    var p = priorities
    var idx = location
    
    while true {
        if p.contains(where: { $0 > p[0] }) {
            var peek = p.removeFirst()
            p.append(peek)
            
            if idx - 1 < 0 {
                // 순서를 앞으로 당기는 것이 아닌 끝순서로 가야함
                idx = p.count - 1
            } else {
                // 앞으로 한칸 당겨짐
                idx -= 1
            }
        } else {
            if idx == 0 {
                // 원래 요소의 개수 - 남은 작업의 개수 + 1 (인덱스 였기때문에)
                return priorities.count - p.count + 1
            }
            
            let _ = p.removeFirst()
            idx -= 1
        }
    }
}