deque란

deque(데크)란 ‘Doble Ended Queue’의 약어로 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조를 말합니다.

코틀린에서는 java.util.Deque를 사용하여 구현할 수 있습니다.

Deque는 큐(Queue)와 스택(Stack)의 특징을 모두 가지고 있습니다.

따라서, 큐와 스택의 모든 연산을 지원하며, 양쪽에서의 삽입과 삭제가 가능하다.

코틀린에서는 Deque를 사용하기 위해서는 먼저 java.util 패키지를 Import 해야합니다

import java.util.*

Deque를 생성하기 위해서는 Deque 인터페이스를 구현한 LinkedList를 사용하면 된다.

즉 LinkedList를 Deque로 업캐스팅해서 사용하면된다.

val deque: Deque<String> = LinkedList()

위와 같이 LinkedList를 사용하여 Deque를 생성한 후, 다음과 같은 연산이 가능

Deque에 요소 추가하기

Deque에 요소를 추가할 때는, addFirst(), addLast() 메소드를 사용

deque.addFirst("First")
deque.addLast("Last")

위의 코드에서 addFirst()는 Deque의 맨 앞에 요소를 추가하고, addLast()는 Deque의 맨 뒤에 요소를 추가 합니다.

Deque에서 요소 제거하기

Deque에서 요소를 제거할 때는, removeFirst(), removeLast() 메소드를 사용

deque.removeFirst()
deque.removeLast()

위의 코드에서 removeFirst()는 Deque의 맨 앞에 있는 요소를 제거하고, removeLast()는 Deque의 맨 뒤에 있는 요소를 제거합니다.

Deque에서 요소 가져오기

Deque에서 요소를 가져올 때는, getFirst(), getLast() 메소드를 사용합니다.

val firstElement = deque.fisrt
val lastElement = deque.last

위의 코드에서 getFirst()는 Deque의 맨 앞에 있는 요소를 반환하고, getLast()는 Deque의 맨 뒤에 있는 요소를 반환합니다.

Deque는 양쪽에서 삽입과 삭제가 가능하기 때문에, 스택과 큐의 연산을 모두 지원하며, 양쪽에서의 요소 접근이 가능

Deque 시간복잡도

일반적인 Deque의 시간복잡도는 아래와 같다

- 요소 추가: O(1)
- 요소 제거: O(1)
- 요소 가져오기: O(1) // 첫 요소 , 마지막 요소 가져오기에 대해서

Deque를 활용한 문제

1. BOJ 10866 덱

풀이

---

deque를 이용한 덱을 구현한 코드

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val sb = StringBuilder()
    val n = br.readLine().toInt()
    val deque : Deque<Int> = LinkedList()
    repeat(n) {
        val cmd = br.readLine().split(" ")
        when (cmd[0]) {
            "push_front" -> deque.addFirst(cmd[1].toInt())
            "push_back" -> deque.addLast(cmd[1].toInt())
            "pop_front" -> sb.append(if (isEmpty(deque)) -1 else deque.removeFirst()).append("\n")
            "pop_back" -> sb.append(if (isEmpty(deque)) -1 else deque.removeLast()).append("\n")
            "size" -> sb.append(deque.size).append("\n")
            "empty" -> sb.append(if (isEmpty(deque)) 1 else 0).append("\n")
            "front" -> sb.append(if (isEmpty(deque)) -1 else deque.first).append("\n")
            "back" -> sb.append(if (isEmpty(deque)) -1 else deque.last).append("\n")
        }
    }
    print(sb.toString())
}

fun isEmpty(deque : Deque<Int>): Boolean = deque.size == 0

LinkedList를 이용해 덱을 구현한 코드

fun main() {
    val br = System.`in`.bufferedReader()
    val sb = StringBuilder()
    val n = br.readLine().toInt()
    val arrayList = ArrayList<Int>()
    repeat(n) {
        val cmd = br.readLine().split(" ")
        when (cmd[0]) {
            "push_front" -> arrayList.add(0, cmd[1].toInt())
            "push_back" -> arrayList.add(cmd[1].toInt())
            "pop_front" -> sb.append(if (isEmpty(arrayList)) -1 else arrayList.removeFirst()).append("\n")
            "pop_back" -> sb.append(if (isEmpty(arrayList)) -1 else arrayList.removeLast()).append("\n")
            "size" -> sb.append(arrayList.size).append("\n")
            "empty" -> sb.append(if (isEmpty(arrayList)) 1 else 0).append("\n")
            "front" -> sb.append(if (isEmpty(arrayList)) -1 else arrayList.first()).append("\n")
            "back" -> sb.append(if (isEmpty(arrayList)) -1 else arrayList.last()).append("\n")
        }
    }
    print(sb.toString())
}

fun isEmpty(arrayList: ArrayList<Int>): Boolean = arrayList.size == 0

2. BOJ 1021 회전하는 큐

풀이

---

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val deque: Deque<Int> = LinkedList()
    //덱 크기 n
    //m 은 뽑을 개수
    val (n, m) = br.readLine().split(" ").map { it.toInt() }

    //고유한 인덱스를 저장한다고 생각
    for (i in 1 .. n){
        deque.addLast(i)
    }
    // 횟수
    var count = 0
    // 뽑을 거
    val choiceList = br.readLine().split(" ").map { it.toInt() }
    // 뽑을거 하나 정해서
    for (choice in choiceList){
        val first = deque.indexOfFirst { it == choice }
        val last = deque.size - first
        // 최단 거리로
        count += if (first >= last){
            repeat(last){
                val tmp = deque.removeLast()
                deque.addFirst(tmp)
            }
            deque.removeFirst()
            last
        }else{
            repeat(first) {
                val tmp = deque.removeFirst()
                deque.addLast(tmp)
            }
            deque.removeFirst()
            first
        }
    }
    println(count)
}

3. BOJ 5430 AC

풀이

---

fun main() {
    val br = System.`in`.bufferedReader()
    val sb = StringBuilder()
    val t = br.readLine().toInt()
    outer@ for (i in 0 until t) {
        val p = br.readLine()
        val n = br.readLine().toInt()
        val list = br.readLine().drop(1).dropLast(1).split(",").toMutableList()
        if (n == 0 && p.contains('D')) {
            sb.append("error").append("\n")
            continue@outer
        }
        //R 뒤집기
        //D 버리기
        // flag가 true면 removefirst 아니면 removelast
        var flag = true
        for (cmd in p) {
            try {
                when (cmd) {
                    'R' -> flag = !flag
                    'D' -> if (flag) list.removeFirst() else list.removeLast()
                }
            } catch (e: NoSuchElementException) {
                sb.append("error").append("\n")
                continue@outer
            }
        }
        val tmp = if (flag) list.joinToString(",") else list.reversed().joinToString(",")
        sb.append("[$tmp]").append("\n")
    }
    println(sb.toString())
}