03-5 스택과 큐
스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조이다. 스택과 큐는 구조는 비슷하지만 처리 방식이 다르다.
[스택 핵심 이론]
- 스택은 삽입과 삭제 연산이 후입선출 LIFO로 이뤄지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
[파이썬의 스택]
- 위치: top(삽입과 삭제가 일어나는 위치)
- 연산(리스트의 이름이 s일 때)
- s.append(data): top 위치에 새로운 데이터를 삽입하는 연산
- s.pop(): top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
- s[-1]: top 위치에 현재 있는 데이터를 단순 확인하는 연산
- 스택은 깊이 우선 탐색 DFS, 백트래킹 종류의 코딩 테스트에 효과적이다. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하다.
[큐 핵심 이론]
- 큐는 삽입과 삭제 연산이 선입선출 FIFO로 이뤄지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.
- 새 값 추가는 큐의 rear, 삭제는 큐의 front에서 이뤄진다.
- 파이썬에서는 일반적으로 deque로 큐를 구현한다.
[파이썬의 스택]
- 위치
- rear: 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front: 큐에서 가장 앞의 데이터를 가리키는 영역이다.
- 연산(리스트의 이름이 s일 때)
- s.append(data): rear 부분에 새로운 데이터를 삽입하는 연산이다.
- s.popleft(): front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- s[0]: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.
- 큐는 너비 우선 탐색 BFS에서 자주 사용하므로 이 역시도 스택과 함께 잘 알아두어야 하는 개념이다.
[우선순위 큐]
- 우선순위 큐(priority queue)는 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
- 우선순위 큐는 일반적으로 힙을 이용해 구현하는데, 힙은 트리 종류 중 하나이다. 6장에서 공부할 예정이다.
📌 문제 011) 스택으로 수열 만들기
시간 제한 2초, 실버 III, 백준 1874번
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
8 # 수열의 개수 4 3 6 8 7 5 2 1
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
+ + + + - - + + - + + - - - - -
1단계 문제 분석
-
현재 수열 값 >= 자연수
- 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push(append)한다. 그리고 push(append)가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.
- 예를 들어, 현재 수열 값이 4이면 스택에는 1, 2, 3, 4를 push(append)하고 마지막에 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나온다. 자연수는 5가 된다.
- 현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push(append)한다. 그리고 push(append)가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.
-
현재 수열 값 < 자연수
- 현재 수열 값이 자연수보다 크다면 pop으로 스택에 있는 값을 꺼낸다. 꺼낸 값이 현재 수열 값이거나 아닐 수 있다. 만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로 NO를 출력한 후 문제를 종료하고, 현재 수열 값이라면 그대로 조건문을 빠져나온다.
- 예를 들어, 자연수는 5, 현재 수열 값은 3이므로 스택에서 3을 꺼낸다. 현재 수열 값과 스택에서 꺼낸 값은 같으므로 계속해서 스택 연산을 수행할 수 있다. 스택에는 1, 2가 남아 있으며, 자연수는 5다.
- 현재 수열 값이 자연수보다 크다면 pop으로 스택에 있는 값을 꺼낸다. 꺼낸 값이 현재 수열 값이거나 아닐 수 있다. 만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로 NO를 출력한 후 문제를 종료하고, 현재 수열 값이라면 그대로 조건문을 빠져나온다.
2단계 슈도 코드
N(수열 개수) A(수열 리스트)
A 수열 리스트 채우기
for N만큼 반복:
if 현재 수열값 >= 오름차순 자연수:
while 현재 수열값 >= 오름차순 자연수:
append()
오름차순 자연수 1 증가
(+) 저장
pop()
(-) 저장
else 현재 수열값 < 오름차순 자연수:
pop()
if 스택 pop 결괏값 > 수열의 수:
NO 출력
else:
(-) 저장
if NO 값을 출력한 적이 없으면:
저장한 값 출력3단계 코드 구현
N = int(input())
A = [0] * N
for i in range(N):
A[i] = int(input())
stack = []
num = 1
result = True
answer = ""
for i in range(N):
su = A[i]
if su >= num: # 현재 수열값 >= 오름차순 자연수: 값이 같아질 때까지 append() 수행
while su >= num:
stack.append(num)
num += 1
answer += "+\n"
stack.pop()
answer += "-\n"
else: # 현재 수열값 < 오름차순 자연수: pop()을 수행해 수열 원소를 꺼냄
n = stack.pop()
# 스택의 가장 위의 수가 만들어야 하는 수열의 수보다 크면 수열을 출력할 수 없음
if n > su:
print("NO")
result = False
break
else:
answer += "-\n"
if result:
print(answer)📌 문제 012) 오큰수 구하기
시간 제한 1초, 골드 IV, 백준 17298번
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
4 3 5 2 7
출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
5 7 7 -1
1단계 문제 분석
- N의 최대 크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다.
- 스택을 활용하자.
[핵심 아이디어]
- 스택에 새로 들어오는 수가 top에 존재하는 수보다 크면 그 수는 오큰수가 된다.
- 오큰수를 구한 후 수열에서 오큰수가 존재하지 않는 숫자에 -1을 출력해야 한다.
2단계 슈도 코드
N(수열 개수) A(수열 리스트) ans(정답 리스트)
A 수열 리스트 채우기
myStack(스택 선언)
for i를 N만큼 반복:
while 스택이 비지 않고, 현재 수열값이 top에 해당하는 수열보다 클 때까지:
스택에서 pop한 값을 index로 하는 정답 리스트 부분을 수열 리스트의 현재 값(A[i])으로 저장
스택에 i의 값을 저장
while 스택이 빌 때까지:
스택에 있는 index의 정답 리스트에 -1 저장
정답 리스트 출력3단계 코드 구현
import sys
n = int(input())
ans = [0] * n
A = list(map(int, input().split()))
myStack = []
for i in range(n):
# 스택이 비어 있지 않고 현재 수열이 스택 top 인덱스가 가리키는 수열보다 클 경우
while myStack and A[myStack[-1]] < A[i]:
ans[myStack.pop()] = A[i] # 정답 배열에 오큰수를 현재 수열로 저장하기
myStack.append(i)
while myStack: # 반복문을 다 돌고 나왔는데 스택이 비어 있지 않다면 빌 때까지
ans[myStack.pop()] = -1 # 스택에 쌓인 index에 -1을 넣기
for i in range(n):
sys.stdout.write(str(ans[i]) + " ")