📌 "LIFO, FIFO, push & pop! 스택과 큐를 이용해서 문제를 풀어보세요."
출제빈도 : 보통
평균점수 : 높음
스택(Stack)이란?
- 먼저 들어온 데이터가 나중에 나가는 선입후출(LIFO) 형식의 자료구조
- 입구와 출구가 동일한 형태
- 삽입(push)와 삭제(pop)은 top에서만 일어난다.
스택 동작예시
삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제()
-> 삽입(1) -> 삽입(4) -> 삭제()
5
5 2
5 2 3
5 2 3 7
5 2 3
5 2 3 1
5 2 3 1 4
5 2 3 1파이썬으로 스택 구현하기
파이썬에서 스택은 따로 자료구조를 제공하지 않고, 리스트로 구현한다.
stack = [] # 빈 스택 선언
stack.append(k) # 삽입 (push)
stack.pop() # 삭제 (pop)
stack[-1] # top에 접근큐(Queue)란?
- 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 형식의 자료구조
- 입구와 출구가 모두 뚫려있는 터널과 같은 형태
- 삽입(enqueue)과 삭제(dequeue)가 반대쪽에서 일어난다.
큐 동작예시
삽입(5) -> 삽입(2) -> 삽입(3) -> 삽입(7) -> 삭제()
-> 삽입(1) -> 삽입(4) -> 삭제()
5
5 2
5 2 3
5 2 3 7
2 3 7
2 3 7 1
2 3 7 1 4
3 7 1 4파이썬으로 큐 구현하기
파이썬에서 큐는 collections의 deque 라이브러리를 사용한다.
from collections import deque
queue = deque() # 빈 큐 선언
queue.append(k) # 삽입 (enqueue)
queue.popleft() # 삭제 (dequeue)queue 라이브러리도 있긴 한데 스택과 큐의 장점을 모두 채택한 deque를 쓰는 것이 효율적이고 간단하다.
나중에 BFS를 풀때 deque가 많이 사용된다고 한다.
코드
1. 기능개발 (Lv. 2)
작업과 속도를 동시에 돌면서 개발완료까지 며칠이 남았는지를 계산해 큐에 넣는다. 그리고 큐에서 하나씩 빼면서 방금 빠진 애보다 큰 애가 나올때까지 모두 뺀다(=한꺼번에 배포한다).
deque를 활용하려고 하다보니 while 안에 또 while이 들어가는게 찜찜해서 다른 사람들의 풀이를 봤는데 11번째줄부터 코드를
# queue = 작업 완료까지 남은 날들
cnt = 0
temp = queue[0] # 첫번째 작업 배포
for i in range(len(queue)):
if temp < queue[i]: # 현작업보다 더 오래 걸리는 작업이 나오면
answer.append(cnt) # 이전까지의 모든 작업 cnt개를 배포
temp = queue[i] # 다음 배포 기준 변경
cnt = 0 # 배포할 작업 수 초기화
cnt += 1 # 현작업보다 적게 걸리는 작업 cnt개
answer.append(cnt)이런식으로 고치면 아마 이중 while문을 쓰지 않고도 가능할 듯 하다. (돌려보진 않음) 근데 이러면 굳이 deque를 쓰는 의미는 없는 것 같다.
2. 올바른 괄호 (Lv. 2)
(이 나오면 스택에 넣고, )이 나오면 스택의 top이 (인지 확인한 다음 (이면 top을 pop시키고, 그렇지 않다면 )도 스택에 쌓는다. 모든 작업이 끝난 후에 스택이 비어있다면 올바른 괄호로 구성된 것이다.
3. 프로세스 (Lv. 2)
현재 큐에 있는 값들 중 최대값을 구해놓고, 가장 왼쪽에 있는 값을 뺀다. 최대값과 방금 뺀 값을 비교했을때 방금 뺀 값이 최대값보다 작으면 다시 큐에 넣고, 그렇지 않다면 그대로 제거한다.
4. 다리를 지나는 트럭 (Lv. 2)
waiting에는 대기 중인 트럭이, going에는 다리를 건너는 중인 트럭이 담긴다.
다리를 건너는 트럭이 있고, (현재 시간 - 다리를 건너기 시작한 시간)이 다리 길이 이상이 되면 다리를 모두 건넜다는 의미이므로 going에서 트럭을 내보낸다.
대기 중인 트럭이 있고, 첫번째 대기트럭의 무게와 현재 다리를 건너고 있는 트럭들의 무게의 합이 다리의 한계치 이하이면 waiting에서는 트럭을 내보내고, going에는 트럭이 들어온다.
going과 waiting이 모두 빈 상태가 되면 모든 트럭이 다리를 건넌 것이다.
5. 주식가격 (Lv. 2)
문제 가독성이 똥망이라(ㅡ.ㅡ) 헤맸다.
주식가격을 차례대로 보면서 스택의 top에 있는 주식가격(=직전까지의 주식가격)이 현재 주식가격보다 큰 동안 pop시킨다. 그리고 현재 인덱스에서 주식가격이 떨어지기 시작했던 지점의 인덱스를 뺀다.
느낀점
- 단순히 리스트를 사용할때보다
deque를 사용했을 때 속도가 진짜 엄청 빨랐다. 🏃=33 - 데이터를 왼쪽에서부터 뺄때
popleft()가 진짜 편하다. - 스택/큐의 성질을 활용할 것이냐, 그냥 리스트(완전탐색?)로 구현할 것이냐로 약간 문제풀이의 결이 달라지는 느낌이다. 그때그때 더 효율적인 방식으로 구현해야할 듯 하다.
