/* 본 게시물은 ' 뇌를 자극하는 알고리즘 | with 박상현 ' 의 내용과 참고자료를 토대로 작성되었습니다. */
/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
참고 자료
[백준] 10028번 - 스택 : https://www.acmicpc.net/problem/10828
1. 스택이란?
'스택'의 사전적 의미는 건초나 짚더미와 같은 뭔가를 쌓아놓은 더미를 뜻한다. 자료구조의 스택 또한 데이터를 아래에서부터 위로 쌓아 얹어 올리도록 하는 자료구조이다. 스택은 중간에 데이터를 삽입하거나 삭제하는 것을 허용하지 않는다. 데이터의 입/출력은 오로지 스택의 꼭대기에서만 이루어진다. 즉, 스택은 '선입후출' (First In - Last out) 의 특징을 가진다.
스택 주요 기능
스택의 주요 기능은 '삽입(push)' 과 '제거(pop)' 두 가지이다. 삽입 연산은 스택 위에 새로운 노드를 '쌓는' 작업이고, 제거 연산은 제일 위에 있는 스택을 '제거' 하는 작업이다.
2. 스택 구현 (백준 10828번)
백준 10828번 - 스택에서 주어진 문제를 풀어보자. 문제는 다음과 같다.
문제
정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 다섯 가지이다.
- push X: 정수 X를 스택에 넣는 연산이다.
- pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 스택에 들어있는 정수의 개수를 출력한다.
- empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
- top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
배열로 스택 구현
먼저 배열로 스택과 주요 기능인 push, pop 을 구현해보자. 배열로 구현할 경우 동적으로 스택의 용량을 조절하기 어렵다는 단점이 있지만, 구현은 간단하다는 장점이 있다. 배열을 이용한 스택 구현은 다음과 같다.
class Stack {
var capacity = 10
var size = 0
var arr = IntArray(capacity)
fun push(element: Int){
if (size < capacity){
arr[size] = element
size++
}
else {
// 데이터 복사
val tmpArr = IntArray(capacity + 10)
for (i in arr.indices){
tmpArr[i] = arr[i]
}
arr = tmpArr
capacity += 10
arr[size] = element
size++
}
}
fun pop(){
println(arr[size - 1])
arr[size - 1] = 0
size--
}
}배열은 정적이기 때문에 데이터를 추가하려면 새로운 배열을 만들어 데이터를 옮겨야한다. 하나 추가할 때 마다 새로운 배열을 만드는 것은 비용이 많이 들기 때문에 배열에 여유 공간(capacity)를 준다. 여기서는 기본 capacity로 10으로 설정하고 배열의 크기를 넘길 시 10개의 공간을 추가한다. (사실 ArrayList 를 사용하는 것이랑 거의 비슷하다.)
나머지 문제 조건을 충족시키기 위한 코드를 추가한다.
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
val stack = Stack()
val testTime = readLine()!!.toInt()
for (i in 1..testTime){
val st = StringTokenizer(this.readLine())
val order = st.nextToken()
when (order){
"push" -> {
stack.push(st.nextToken().toInt())
}
"top" -> {
if (stack.size == 0) println(-1) else println(stack.arr[stack.size - 1])
}
"empty" -> {
if (stack.size == 0) println(1) else println(0)
}
"pop" ->{
if(stack.size == 0) println(-1) else stack.pop()
}
"size" -> println(stack.size)
}
}
}실행 결과 (416ms / 17636 KB)
위 코드를 그대로 실행하면 시간초과 (0.5초) 가 뜬다. 문제에서는 명령어를 1~10000 사이로 주는데 만약 push 가 10000번 일 경우는 배열의 용량을 초과하는 경우가 많기 때문에 새로운 배열을 만드는 과정이 많을 것이다. 그래서 처음 capacity를 10 -> 10000으로 수정할 시 시간 초과가 안뜬다.
var capacity = 10000이를 통해 배열로 만든 스택의 단점을 확인할 수 있다.
링크드 리스트로 스택 구현
class StackByList(){
val list = LinkedList<Int>()
class LinkedList<T> {
data class Node<T>(
var data: T?,
var next: Node<T>?
)
private var headNode: Node<T>? = null
var lastNode: Node<T>? = null
var currentSize: Int = 0
fun addLast(data: T){
val newNode = Node(data, null)
//headNode 가 비어있는 경우 즉, 요소가 없는 경우
if (headNode == null){
headNode = newNode
lastNode = newNode
currentSize++
return
}
lastNode?.next = newNode
lastNode = newNode
currentSize++
}
private fun removeFirst(){
// Empty List
if (headNode == null){
return
}
// headNode == lastNode -> 요소 1개
if (headNode == lastNode){ // or headNode.next == null or currentSize == 1
println(lastNode?.data)
lastNode = null
headNode = null
}
else {
headNode = headNode?.next
}
currentSize--
}
fun removeLast(){
//Empty List
if (headNode == null){
return
}
// 요소 1개
if (headNode == lastNode){
return removeFirst()
}
//임시 포인터
var currentNode = headNode
var prevNode: Node<T>? = null
//lastNode 이전 노드 즉 마지막에서 두번째 node
while (currentNode != lastNode){
prevNode = currentNode
currentNode = currentNode?.next
}
// currentNode == lastNode
println(currentNode?.data)
prevNode?.next = null
lastNode = prevNode
currentSize--
}
}
}사실 코틀린의 linkedList를 이용하면 되지만 복습하는 차원에서 다시 구현해봤다.
실행 결과 (444ms, 23472KB)
결과만 놓고 보면 배열의 성능이 우수하다고 생각할 수 있다. 하지만 배열은 Array 크기를 이미 10000(문제에서 주어진 최대 값)으로 설정해놓고 테스트를 진행했기 때문에 만약 문제에서 준 데이터 개수를 몰랐더라면 링크드리스트로 만든 Stack이 더 좋은 성능을 보였을 것이다.
스택 구현 끝.
다음 해볼 것은 큐!
