leetcode 232. Implement Queue using Stacks 문제 풀이

문제

https://leetcode.com/problems/implement-queue-using-stacks/description/

제출 코드

class MyQueue {
    private var input: [Int] = []
    private var output: [Int] = []

    init() {}
    
    func push(_ x: Int) {
        input.append(x)
    }
    
    func pop() -> Int {
        if output.isEmpty {
            output = input.reversed()
            input.removeAll()
        }
        return output.removeLast()
    }
    
    func peek() -> Int {
		    // Constraints 중 "All the calls to pop and peek are valid."
		    // pop이나 peek를 호출할 때 큐에 적어도 하나의 요소가 항상 존재함을 보장한다는 의미
		    // 강제바인딩 사용을 허용해도 된다고 판단
        guard output.isEmpty else { return output.last! }
        return input.first!
    }
    
    func empty() -> Bool {
        return input.isEmpty && output.isEmpty
    }
}

개선 코드

class MyStack<T> {
    private var elements: [T]
    
    init(elements: [T] = []) {
        self.elements = elements
    }
    
    func push(_ x: T) {
        elements.append(x)
    }
    
    func pop() -> T {
        elements.removeLast()
    }
    
    func first() -> T? {
        elements.first
    }
    
    func last() -> T? {
        elements.last
    }
    
    func isEmpty() -> Bool {
        elements.isEmpty
    }
    
    func reversed() -> [T] {
        elements.reversed()
    }
    
    func clear() {
        elements.removeAll()
    }
}

class MyQueue {
    private var input: MyStack<Int> = MyStack()
    private var output: MyStack<Int> = MyStack()

    init() {}
    
    func push(_ x: Int) {
        input.push(x)
    }
    
    func pop() -> Int {
        if output.isEmpty() {
            output = MyStack(elements: input.reversed())
            input.clear()
        }
        return output.pop()
    }
    
    func peek() -> Int {
        guard output.isEmpty() else { return output.last()! }
        return input.first()!
    }
    
    func empty() -> Bool {
        input.isEmpty() && output.isEmpty()
    }
}

개선된 점

1. Stack 객체 정의
   • 개선 전
     • Queue 기능은 기대한 것처럼 동작하지만, 내부 코드를 보면 두개의 배열로 구성되어있어 코드만 봤을 때 두 개의 스택으로 큐를 구성된건지 알 수 없음
   • 개선 후
     • Stack 역할을 객체로 캡슐화하면서 각 클래스의 역할과 책임이 명확하게 분리되었고, Queue의 동작이 두 개의 스택으로 구성되는 것을 한눈에 알 수 있음
     • 객체 역할 분리를 통해 OOP 준수 및 (실제 제품코드였다면) 코드 유지보수성 향상

⏱️ 시간복잡도

• 개선전과 개선후의 시간복잡도는 O(1)로 동일합니다.

📦 공간복잡도

• 개선전과 개선후의 공간복잡도도 입력 요소 수에 따라 O(n)로 동일합니다.
• MyStack 클래스 추가로 인한 오버헤드는 미미하기 때문에 성능 측면에서 큰 차이는 없습니다.

💨 실행속도

• 개선전과 개선후 실행속도도 0ms로 동일합니다.

회고

• 문제 풀이 접근 방식은 잘 유추했는데, 확신이 없어 결국 구글링을 했던 것이 아쉽다. 좀 더 끈기있게 순수 내 머리에서 나온 방식을 구현해보면 좋을 것 같은데, 아쉽다!🥲
• 처음에는 Queue가 기대하는 것처럼 동작만 하면 될 것이라고 생각해고 내부 프로퍼티를 배열로 선언했는데, 문제 의도 자체가 두 개의 Stack으로 하나의 Queue를 구성하는 것이기 때문에 Stack을 정의해서 다시 구성해보고 싶었다. 코드가 너무 길어지지 않을까 싶었지만, Queue의 동작과 각 클래스의 역할이 명확해졌고 만약 실제 코테였다면 리뷰를 하게 되었을 때 코드 구현 의도를 더 잘 설명할 수 있을 것 같다는 생각이 들었다.