코틀린 코딩테스트 강좌, 스택과 큐

1. 서론

코딩테스트는 현대 프로그래밍 직업을 찾기 위한 중요한 과정 중 하나입니다. 기술이 발전하고 데이터 구조와 알고리즘의 중요성이 부각됨에 따라 이러한 기술들은 프로그래머로서의 역량을 평가하는 주요한 기준이 되었습니다. 이 강좌에서는 코틀린을 사용하여 스택(Stack)과 큐(Queue)의 개념을 이해하고, 이를 기반으로 한 알고리즘 문제를 해결해 보겠습니다.

2. 스택과 큐의 기본 개념

2.1. 스택(Stack)

스택은 데이터를 저장하는 자료구조 중 하나로, 후입선출(LIFO, Last In First Out) 방식으로 작동합니다. 즉, 가장 나중에 들어온 데이터가 가장 먼저 나가는 구조입니다. 스택은 주로 함수 호출 스택, 브라우저의 뒤로 가기 버튼, 그리고 문자열의 괄호 검증 알고리즘 등에서 사용됩니다.

2.2. 큐(Queue)

큐는 데이터를 저장하는 또 다른 자료구조로, 선입선출(FIFO, First In First Out) 방식으로 작동합니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조입니다. 큐는 주로 프린터 작업 관리, 프로세스 스케줄링, 그리고 너비 우선 탐색(BFS) 알고리즘에서 사용됩니다.

3. 문제 설명

이제 스택과 큐 를 활용한 문제를 해결해 보겠습니다. 다음 문제를 살펴보겠습니다:

문제: 괄호 유효성 검사

주어진 문자열이 올바른 괄호로 이루어져 있는지를 판단하는 함수를 작성하세요. 올바른 괄호란, 모든 열린 괄호가 반드시 닫히고, 모든 닫힌 괄호가 그에 대응하는 열린 괄호와 쌍을 이뤄야 합니다.

예를 들어, 문자열 “{[()]}“는 올바르지만 “{[(])}“는 올바르지 않습니다.

4. 문제 분석

이 문제를 해결하기 위해서는 다음 절차를 따르는 것이 좋습니다:

문자열을 순회하면서 열린 괄호를 스택에 저장합니다.
닫힌 괄호를 만났을 때 스택에서 가장 최근에 저장된 열린 괄호와 쌍을 이루는지 확인합니다.
모든 문자를 처리한 후에도 스택이 비어 있지 않다면, 문자열은 유효하지 않습니다.

5. 알고리즘 설계

따라서 다음과 같은 알고리즘을 설계할 수 있습니다:

스택을 초기화합니다.
문자열의 각 문자를 순회합니다.
문자열의 각 문자가 열린 괄호인 경우, 스택에 추가합니다.
닫힌 괄호인 경우, 스택에서 값을 꺼내어 매칭되는 열린 괄호인지 확인합니다.
스택이 비어있지 않다면, 문자열은 유효하지 않으며 false를 반환합니다.
문자를 모두 처리한 후 스택이 비어 있다면 true를 반환합니다.

6. 코틀린 구현

위에서 설명한 알고리즘을 코틀린으로 구현해 보겠습니다.

fun isValidParentheses(s: String): Boolean {
    val stack = mutableListOf()
    val mapping = mapOf('(' to ')', '{' to '}', '[' to ']')

    for (char in s) {
        if (mapping.containsKey(char)) {
            stack.add(char)
        } else if (stack.isNotEmpty() && mapping[stack.last()] == char) {
            stack.removeAt(stack.size - 1)
        } else {
            return false
        }
    }
    return stack.isEmpty()
}

7. 코드 설명

코드의 각 부분은 다음과 같은 역할을 합니다:

val stack = mutableListOf(): 스택을 초기화합니다.
val mapping = mapOf('(' to ')', '{' to '}', '[' to ']'): 열린 괄호와 닫힌 괄호의 매핑을 저장합니다.
for (char in s): 문자열의 각 문자를 순회합니다.
if (mapping.containsKey(char)): 열린 괄호인 경우 스택에 추가합니다.
else if (stack.isNotEmpty() && mapping[stack.last()] == char): 닫힌 괄호라면 매칭되는 열린 괄호가 스택의 가장 위에 있는지 확인하고, 매칭된다면 스택에서 제거합니다.
문자열 처리 후 스택이 비어 있으면 true, 그렇지 않으면 false를 반환합니다.

8. 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. n은 문자열의 길이입니다. 왜냐하면 각 문자를 한 번만 처리하기 때문입니다. 공간 복잡도는 O(n)으로, 이는 최악의 경우 스택에 모든 열린 괄호가 저장될 수 있기 때문입니다.

9. 테스트 케이스

다음과 같은 테스트 케이스를 사용하여 구현이 올바른지 확인할 수 있습니다.

fun main() {
    println(isValidParentheses("{[()]}")) // true
    println(isValidParentheses("{[(])}")) // false
    println(isValidParentheses("{{[[(())]]}}")) // true
    println(isValidParentheses("{")) // false
    println(isValidParentheses("}")) // false
}

10. 결론

이번 강좌에서는 스택과 큐의 기본 개념과 함께, 스택을 이용한 괄호 유효성 검증 문제를 해결해 보았습니다. 이러한 접근법은 코딩 테스트에서 자주 출제되는 문제 유형 중 하나이므로, 충분한 연습을 통해 스택과 큐의 사용에 익숙해지는 것이 중요합니다.

11. 참고 자료

LeetCode: Valid Parentheses
GeeksforGeeks: Stack Data Structure
Wikipedia: Stack (abstract data type)

이제 독자 여러분도 코틀린을 사용하여 스택과 큐의 개념을 이해하고, 다양한 문제를 풀어보시기 바랍니다.