Stack(스택) feat.kotlin

정의

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다.

그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

 

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.

 

kotlin의 collections는 java의 collections 라이브러리를 그대로 사용한다. 

stack 역시 java.util.stack 패키지에서 가져와서 사용한다.

 

Stack의 모든 연산은 목록의 제일 위(마지막)에서 일어나기에 필수 연산은 모두 상수 시간의 시간 복잡도를 갖는다.

• 삽입(Push): O(1) 
• 삭제(Pop): O(1)
• 읽기(Peek): O(1) 
• 탐색(search): O(n)  - 모든 요소를 다 확인해야 된다.

스택의 사용 예시 

1. 짝 맞추기.

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

4949번: 균형잡힌 세상

문제 분석

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

입력값에서 괄호들을 구별해 내어 그것이 서로 짝을 맞추어 있는지 확인하는 문제이다.

여기서 스택의 가장 중요한 성질

 

LIFO - Last In First Out

여러 개의 괄호 들이 있을때 가장 안쪽 괄호 부터 바깥쪽까지 모든 괄호의 짝이 맞아야 된다.

즉,  나중에 들어온 괄호부터 짝을 맞춰서 사라져야 한다.

import java.util.Stack

fun main() = with(System.`in`.bufferedReader()) {

    val stack = Stack<Char>()
    val charArr = arrayOf('(', ')', '[', ']')

    while (true) {

        val str = readLine().toString()
        if (str == ".") break

        stack.clear()
        for (i in 0 until str.length) {
            // stack이 비어있고, 괄호라면. 넣음.
            if (stack.empty() && str[i] in charArr) {
                stack.add(str[i])
                continue
            }
            // 괄호짝 맞추기.
            if (stack.isNotEmpty() && str[i] in charArr) {
                if (str[i] == ')' && stack.peek() == '(') {
                    stack.pop()
                } else if (str[i] == ']' && stack.peek() == '[') {
                    stack.pop()
                } else {
                    stack.add(str[i])
                }
                continue
            }
            // 1문장 종료.
            if (str[i] == '.')
                break
        }
        // 스택이 비어 있으면 모든 짝이 맞았기 때문이고,
        // 스택이 비어 있지 않다면, 왼쪽이던 오른쪽이던 스택에 짝이 맞지 않는 상태로 남아 있다.
        if (stack.isEmpty()) {
            println("yes")
        } else {
            println("no")
        }
    }
}

 

2. 후위 표기식

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

1918번: 후위 표기식

문제 분석

 

중위 표기식 --> 후위 표기식

 

- 연산자와 피연산자를 구별하기.

- 연산자를 stack에 담아 두었다가 우선순위에 따라 pop하여 위치를 정함.

즉, 자신 보다 우선순위가 같거나 높은것을 모두 꺼내어 처리하고 자신이 들어감.

- 괄호는

여는 괄호는 가장 낮은 우선순위

닫는 부분을 가장 높은 우선순위를 두어서 처리함. 단, 닫는 괄호까지만

 

/*
    후위 표기식
 */


import java.util.*

var str = ""

val result = mutableListOf<Char>()
val stack = Stack<Char>()

val operator = charArrayOf('+', '-', '*', '/')
val operand = CharArray(26) { 'A' + it }
fun main() = with(System.`in`.bufferedReader()) {

    str = readLine()

    for (i in 0 until str.length) {

        // 피연산자 A..Z 라면 결과리스트에 넣음
        if (str[i] in operand) {
            result.add(str[i])
            continue
        }

        // 스택이 비어 있다면, 일단 넣음.
        if (stack.isEmpty()) {
            stack.add(str[i])
        } else {
            if (str[i] == '(') {
                // 여는 괄호는 그냥 넣음.
                stack.add(str[i])
            } else if (str[i] == ')') {
                // 닫는 괄호는 여는 괄호를 만날때 까지 모든 연산자를 꺼냄
                while (stack.isNotEmpty() && stack.peek() != '(') {
                    result.add(stack.pop())
                }
                stack.pop()
            } else if (str[i] in operator) {
                // 연산자라면 자신보다 높거나 같은 순위 연산자를 모두 꺼내고 들어감.
                if (str[i] in arrayOf('+', '-')) {
                    while (stack.isNotEmpty() && stack.peek() in operator) {
                        result.add(stack.pop())
                    }
                    stack.add(str[i])
                } else {
                    while (stack.isNotEmpty() && stack.peek() in arrayOf('*', '/')) {
                        result.add(stack.pop())
                    }
                    stack.add(str[i])
                }
            }
        }
//        println(stack)
    }

    while (stack.isNotEmpty()){
        result.add(stack.pop())
    }

    val sb = StringBuilder()
    for (i in 0 until result.size){
        sb.append(result[i])
    }
    println(sb.toString())
}