[스택] LeetCode 232번 문제 학습

 

문제 설명

Implement Queue using Stacks는 스택을 써서 큐를 구현하는 문제임. 큐의 연산 push, pop, peek, empty를 지원해야 함. push는 요소를 큐 뒤에 추가, pop은 앞에서 제거하고 리턴, peek은 앞 요소 리턴, empty는 큐가 비었는지 확인. 스택은 후입선출(LIFO)이라 선입선출(FIFO) 큐를 구현하려면 스택 조작이 필요함.

 

푼 과정

스택 하나로 풀었음. 슬라이스([]int)를 스택처럼 써서 구현. push는 슬라이스 끝에 append로 추가. pop은 첫 요소 꺼내고 슬라이스 잘라서 리턴. peek은 첫 요소 리턴. empty는 슬라이스 길이 체크. 근데 이건 스택이 아니라 그냥 슬라이스 직접 써서 큐 구현한 거라 문제 의도랑 살짝 안 맞음. 문제는 스택(스택 연산만) 써서 큐를 만들어야 함.

 

그래도 코드 동작은 잘하고 빠르게 풀었음.

---

알고리즘 분석

슬라이스로 큐 직접 구현했음. push는 append로 O(1) 평균, pop은 슬라이스 첫 요소 제거로 O(n) (내부 복사 때문), peek은 O(1), empty도 O(1). 공간은 슬라이스 하나라 O(n). 문제 의도는 스택 두 개 써서 push/pop을 O(1)로 만드는 거였음. 너 방식은 큐 동작은 맞지만 스택 연산(push/pop)만 썼어야 함. 스택 두 개 방식은 push/pop 중 하나를 O(n), 다른 하나를 O(1)로 만듦.

 

package main

type MyQueue struct {
	x []int
}

func Constructor() MyQueue {
	return MyQueue{
		x: make([]int, 0),
	}
}

func (m *MyQueue) Push(x int) {
	m.x = append(m.x, x)
}

func (m *MyQueue) Pop() int {
	p_x := m.x[0]

	m.x = m.x[1:]

	return p_x
}

func (m *MyQueue) Peek() int {
	return m.x[0]
}

func (m *MyQueue) Empty() bool {
	return len(m.x) == 0
}

func main() {
}