Data Structures & Algorithms in Swift
Understanding how data structures and algorithms work in code is crucial for creating efficient and scalable apps and acing job interviews. Swift’s standard library and, more recently, the Swift Collections and Algorithms packages contain a robust set of
www.kodeco.com
Chapter 1: Why Learn Data Structures & Algorithms?
Chapter 3: Swift Standard Library
Chapter 4: Stack Data Structure
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) 이다.
