Chapter 5: Stack Challenges

Stack은 간단하지만, 여러 프로그램에서 사용되는 자료구조이다.

 

Challenge 1: Reverse an Array

배열(Array)의 내용을 역순으로 출력하는 함수를 생성한다.

 

Solution

Stack의 주요 사용 사례 중 하나는 역추적(backtracking)이다. 일련의 값(value)을 Stack으로 push 한 후, 다시 pop하면 역순(reverse order)으로 배열된다.

func printInReverse<T>(_ array:[T]) {
    var stack = Stack<T>()
    
    for value in array {
        stack.push(value)
    }
    
    while let value = stack.pop() {
        print(value)
    }
}

노드를 Stack으로 push하는 시간 복잡도는 O(n) 이고, 값을 출력하기 위해 Stack을 pop하는 시간복잡도 또한 O(n) 이다. 따라서, 전체적인 이 알고리즘의 시간 복잡도는 O(n) 이 된다. 함수 내부에서 Stack을 할당하기 때문에 공간복잡도 또한 O(n) 이 된다.

---

Challenge 2: Balance the parentheses

괄호의 균형을 확인한다. 문자열이 주어지면 '(' 과 ')' 이 있는 지 확인하고, 문자열의 괄호가 균형이 맞으면 true를 반환한다. 예를 들면 다음과 같다.

// 1 
h((e))llo(world)() // balanced parentheses 
// 2 
(hello world // unbalanced parentheses

 

Solution

문자열에 괄호가 균형으로 되어 있는지 판단하기 위해 문자열의 각 문자(character)를 확인해야 한다. '('가 있으면, 이를 Stack에 push한다. 반대로 ')' 가 있다면 Stack에서 pop한다.

func checkParentheses(_ string: String) -> Bool {
    var stack = Stack<Character>()
    
    for character in string { //문자열의 character를 loop
        if character == "(" { //"(" 를 push
            stack.push(character)
        } else if character == ")" { //")" 를 pop
            if stack.isEmpty {
                return false
            } else {
                stack.pop()
            }
        }
    }
    
    return stack.isEmpty
    //문자열 loop가 끝났을 때, Stack이 비어 있으면 괄호가 균형적으로 된 문자열이다.
}

이 알고리즘의 시간복잡도는 O(n) 이며, 여기서 n은 문자열의 문자 수 이다. 또한, Stack 자료구조를 사용하므로 공간복잡도 역시 O(n) 이다.