[코틀린] 10866번 덱

package 알고리즘.백준.덱

import java.io.BufferedReader
import java.io.InputStreamReader

/**
 *packageName    : 알고리즘.백준.덱
 * fileName       : Main
 * author         : ipeac
 * date           : 2024-03-02
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2024-03-02        ipeac       최초 생성
 */
fun main() {
    BufferedReader(InputStreamReader(System.`in`)).use { br ->
        val n = br.readLine().toInt()
        val deque = ArrayDeque<Int>()
        val answer = StringBuilder()
        
        repeat(n) {
            when (val command = br.readLine()) {
                "pop_front" -> answer.appendLine(deque.removeFirstOrNull() ?: -1)
                "pop_back" -> answer.appendLine(deque.removeLastOrNull() ?: -1)
                "size" -> answer.appendLine(deque.size)
                "empty" -> answer.appendLine(if (deque.isEmpty()) 1 else 0)
                "front" -> answer.appendLine(deque.firstOrNull() ?: -1)
                "back" -> answer.appendLine(deque.lastOrNull() ?: -1)
                
                else -> {
                    val (p, x) = command.split(" ")
                    when (p) {
                        "push_front" -> deque.addFirst(x.toInt())
                        "push_back" -> deque.addLast(x.toInt())
                    }
                }
            }
        }
        
        println(answer)
    }
}

• 덱(Deck) 관련 문제이다
  • 덱까지 구현해서 문제를 풀어보면 좋을 것 같긴하다..

• 일단 ArrayDeck 을 사용하였다.

  ArrayDeck

  • 등장 이유
    • 효율적인 양방향 큐(deque) 의 구현을 위해서 등장
  • 장점
    • 기존의 LinkedList 기반 큐의 경우 추가, 제거시에 O(1) 의 성능을 보인다.
      • ArrayDeck 도 그 면에서는 동일하게 좋다.
    • 메모리 사용량의 최적화
      • LinkedList 같은 연결리스트의 경우 각 노드가 데이터와 함께 다음 노드를 가리키는 포인터를 포함함.
      • 결국 포인트를 가지고 있음으로서, 그 만큼의 메모리의 추가적인 공간이 필요하게 된다.
      • 하지만, ArrayDeck 의 경우 이러한 포인터가 없기에, 단순한 배열 인덱스를 사용하여 요소에 접근한다.
    • 랜덤 엑세스 최적화
      • 배열구조이다.
      • LinkedList 같은 경우 연속한 메모리에 위치한 것이 아니기에, 결국 최악 O(n) 의 조회 성능을 기대할 수 있다.
      • 하지만 ArrayDeck 의 경우 배열 구조이기에 인덱스 를 통한 접근으로 O(1) 시간에 조회가 가능하다.

---

잡설하고, 일단 문제 자체는 너무 쉬웠는데,

단순히 프린트 스트림으로 출력하는 경우 IO 가 반복시마다 발생해서 오버헤드가 있다.

StringBuilder() 에 담아서 해당 값을 한번의 IO 로 출력하도록하면 통과한다.

Uploaded by N2T