[백준 10866번][Kotlin] 덱

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

10866번: 덱

 

난이도 : 실버 4
태그 : 자료구조, 덱

 

---

1. 설명

 

이전에 포스팅했던

스택(https://uknowblog.tistory.com/11?category=989901)과

큐(https://uknowblog.tistory.com/19?category=989901)에 이어

 

또다른 자료구조인 덱을 사용하는 문제입니다.

 

Deque는 덱, 데크, 데큐로도 불리며

한쪽 방향으로만 push / pop이 일어났던 큐와 달리,

양쪽 모두에서 push / pop이 가능한 양방향 큐라고 할 수 있습니다.

 

---

2. 소스코드

      

      

      

    
    

      <code />
    
fun main() {
    val list: LinkedList<Int> = LinkedList()

    val n = readLine()!!.toInt()

    repeat(n) {
        when(val line = readLine()!!) {

            "pop_front" -> {
                if(list.size == 0) println(-1) else println(list.removeFirst())
            }
            "pop_back" -> {
                if(list.size == 0) println(-1) else println(list.removeLast())
            }
            "size" -> {
                println(list.size)
            }
            "empty" -> {
                println(if(list.size == 0) 1 else 0)
            }
            "front" -> {
                if(list.size == 0) println(-1) else println(list.first)
            }
            "back" -> {
                if(list.size == 0) println(-1) else println(list.last)
            }
            else -> {
                if(line.startsWith("push_front")) {
                    list.addFirst(line.split(" ")[1].toInt())
                } else {
                    list.addLast(line.split(" ")[1].toInt())
                }
            }
        }
    }
}

 

링크드리스트를 사용해 구현할 수 있었기에, 소스코드 자체는 큐나 스택보다 간단합니다.

 

 

      

      

      

    
    

      <code />
    
"pop_front" -> {
    if(list.size == 0) println(-1) else println(list.removeFirst())
}
"pop_back" -> {
    if(list.size == 0) println(-1) else println(list.removeLast())
}

pop front/back의 경우 removeFirst와 removeLast를 이용해 처리할 수 있습니다.

 

 

      

      

      

    
    

      <code />
    
"front" -> {
    if(list.size == 0) println(-1) else println(list.first)
}
"back" -> {
    if(list.size == 0) println(-1) else println(list.last)
}

front/back의 경우 list.frist와 list.last를 사용해 처리할 수 있습니다.

 

      

      

      

    
    

      <code />
    
else -> {
    if(line.startsWith("push_front")) {
        list.addFirst(line.split(" ")[1].toInt())
    } else {
        list.addLast(line.split(" ")[1].toInt())
    }
}

startWith는 문자열이 특정 문자열로 시작하는지 판별하는 함수입니다.

 

처음 부분에 삽입할때는 addFirst를, 끝 부분에 삽입할때는 addLast를 사용해 처리할 수 있습니다.

 

 

---

3. 소스코드

 

스택과 큐에 이어 자료구조 문제입니다.

 

자바/코틀린에서는 간단히 링크드리스트를 이용해 풀 수 있었습니다.