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
'자바 > 알고리즘' 카테고리의 다른 글
[코틀린 ] 5525 IOIOI [문자열] (0) | 2024.03.02 |
---|---|
[코틀린] 21736 헌내기는 친구가 필요해 (0) | 2024.03.01 |
[알고리즘] 11659번: 구간 합 구하기 4 (0) | 2024.02.21 |
[알고리즘] 최소 신장 트리 || 최소 스피닝 트리 (MST) (0) | 2024.02.19 |
[알고리즘] 백준 1927 최소 힙 (0) | 2024.02.12 |