자료구조 - 스택과 큐

스택과 큐는 자료구조에 대해 학습하신 분들이라면 이미 잘 알고 있는 내용일 것이기 때문에 자세한 설명은 생략하겠습니다. 스택은 DFS(깊이 우선 탐색), 백 트래킹에 사용되며, 큐는 BFS(너비 우선 탐색)에 사용됩니다.

1. 스택으로 수열 만들기

>> 백준 1874번 / 실버 3

1) Problem

• 1부터 오름차순으로 숫자를 스택에 push한다.
• pop으로 주어진 수열을 만들어내기 위한 push와 pop의 순서를 +와 -로 나타낸다.
  

2) Test Case

3) Solution

import sys
input = sys.stdin.readline

size = int(input()) # 수열의 크기
arr = [0] * size # 수열

for i in range(size):
    arr[i] = int(input())
    
stack = [] # stack 배열
num = 1 # 1부터 push
result = True # +, -로 표현할 수 있음을 의미(파이썬에서는 true 사용 불가)
answer = "" # 문제의 조건을 만족하는 정답

for i in range(size):
    if arr[i] >= num: 
        while arr[i] >= num: # arr[i]와 같아질 때까지 stack에 append
            stack.append(num)
            num += 1 
            answer += "+\n" # 더한 만큼 answer에 +를 덧붙임
        stack.pop() # 마지막 값을 pop하여 수열을 만듦
        answer += "-\n" # pop할 때, answer에 -를 덧붙임 
    else: # 현재 수열의 수가 num보다 작을 때
        n = stack.pop() # stack에서 pop
        if n > arr[i]: # pop한 수가 현재 수열의 수보다 크면 
            print("NO") # 수열 표현 불가(push하면 더 커지고, pop을 2번 하면 원하는 수열이 안 나오므로)
            result = False
            break
        else:
            answer += "-\n"
            
if result:
    print(answer)
        

2. 오큰 수 구하기

>> 백준 17298번 / 골드 4

1) Problem

오큰 수란 인덱스 i의 원소보다 오른쪽에 위치하면서 해당 원소보다 큰 원소들 중 가장 왼쪽에 위치하는 수이다. 만약 조건을 만족하는 수가 없다면, 오큰 수는 -1이 된다.

2) Test Case

3) Solution

스택에 오큰수를 구하고자하는 원소의 index를 append한다. for문을 돌면서 stack에 index를 계속해서 삽입하다가 오큰수가 구해지면(arr[stack[-1]] < arr[i]를 만족) stack에서 pop한다.

import sys
size = int(input()) # 수열의 크기 
arr = list(map(int, sys.stdin.readline().split())) # 수열
answer = [-1] * size # 오큰수 default 배열
stack = [] # initial stack

stack.append(0) # stack에 들어가는 값은 오큰수를 구하려는 원소의 index임 
for i in range(1, size): # size는 범위에 포함 안됨
    while stack and arr[stack[-1]] < arr[i]: # 스택이 비어있지 않고, 스택의 마지막 원소가 인덱스 i인 원소보다 작을 때
        # 오큰 수를 구했으니 stack에서 pop하고 해당 인덱스를 answer 배열의 인덱스로 사용
        answer[stack.pop()] = arr[i] 
        
    stack.append(i) # index는 항상 삽입

print(*answer) # for문으로 answer를 공백을 포함한 문자열로 변환하면 시간초과 발생