백준 3986번 문제 풀이

문제

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

제출 코드 v1

final class StringStack {
    private var characters: [Character] = []
    
    init() {}
    
    func push(_ char: Character) {
        characters.append(char)
    }
    
    func pop() -> Character {
        characters.removeLast()
    }
    
    func peek() -> Character? {
        characters.last
    }
    
    func isEmpty() -> Bool {
        characters.isEmpty
    }
}

var goodWordCount: Int = Int(readLine()!)!
while let input = readLine() {
    let storage = StringStack()
    for char in input {
        if let last = storage.peek() {
            if char == last {
                _ = storage.pop()
            } else {
                storage.push(char)
            }
        } else {
            storage.push(char)
        }
    }
    if !storage.isEmpty() {
        goodWords -= 1
    }
}
print(goodWords)

어떤 점을 고민했을까?

1. 스택 이용 사고력우선 Stack을 Storage 개념으로 생각했고, 문자열을 순회하면서 같은 문자와 매칭되기를 기다리는 문자들을 Storage에 저장했습니다. 매칭된 아치형 곡선이 서로 겹치면 안된다는 전제와 문자열을 순회할 때 매칭을 기다리는 문자가 무엇이고 이전 문자가 무엇인지를 알아야 한다는 조건을 찾으니 LIFO 방식의 Stack 이용이 이해되었습니다.
2. 문자가 저장되다가 같은 문자를 만나 매칭될 때 Storage에서 제거되기 때문에 계속해서 문자열을 순회하다가 매칭되는 문자를 만나도 “매칭된 아치형 곡선이 서로 겹치면 안된다는 전제”를 충족하게 되고, LIFO 방식이기 때문에 pop() 호출했을 때 무조건 이전 문자를 반환하게 되어 이전 문자를 알아야 한다는 풀이 조건도 충족됩니다.
3. 애초에 스택을 이용한다는 힌트를 받았음에도 알고리즘이 떠오르지 않았습니다. 그래서 스택은 LIFO 방식이고 문자열을 하나씩 제거한다는 힌트까지 얻었을 때 비로소 구조가 떠올라서 작성하게 되었습니다.
4. 좋은 단어 카운팅
5. 좋은 단어의 경우 정상적으로 매칭되어 문자열 중 매칭을 기다리는 문자가 없을 것이기 때문에 전체 단어 개수에서 Stack의 isEmpty()를 통해 좋은 단어가 아님을 알게 되는 경우 -1씩 카운팅하여 좋은 단어 개수를 알 수 있도록 작성했습니다.

⏱️ 시간복잡도

• 단어마다 한번씩 순회하고 각 문자마다 Stack 연산을 수행하기 때문에, 스택의 기본 연산 시간복잡도 O(1)에서 단어마다 수행되기 때문에 전체 단어 개수를 N이라고 하여, 전체 시간 복잡도는 O(N)입니다.

📦 공간복잡도

• 저장공간 개념으로 Stack을 사용하기 때문에 최악의 경우 모든 문자가 쌓일 수도 있어 단어의 길이만큼 공간이 필요하여, 단어 하나당 O(n)의 공간 복잡도가 발생합니다.
• 위 코드에서 메모리 재할당 비용을 줄이고자 한다면, let storage = StringStack()을 while문 외부에서 선언하여 순회 후 초기화를 반복하는 코드로 작성할 수 있을 것 같습니다.

💨 실행속도

• 48ms