[알고리즘] stack 문제 비교 (백준 - 2493, 17298, 6198)

아래의 백준 문제는 스택에 관련된 문제입니다. 비슷한듯 접근 방법이 달라 비교하여 정리했습니다!

스택은 언제 사용할까?

💡 2중 for문으로는 시간 초과가 날 것 같을 때 → O(n)에 가까이 갈 수 있도록 하는 스택!

 

탑 (레이저)

문제 = 뒤에서 봤을 때 나보다 큰 수 하나

방향 = ←

뒤에 애들이 나보다 작으면 어차피 가려지므로 의미없음

from collections import deque
n = int(input())
top = list(map(int, input().split()))
stack = []
answer =[0] * n
cnt = 0

for i in range(n):
    while stack:
        if stack[-1][1] < top[i]:
            stack.pop()
        else:
            answer[i]= stack[-1][0] +1
            break
    stack.append((i, top[i]))

print(" ".join(map(str, answer)))

빌딩

문제 = 앞에서 봤을 때 나보다 작은 수 전체

방향 = →

관리할 수 있는 빌딩이 몇개?

입장을 바꿔서 빌딩입장에서 자기가 관리될 수 있는지 확인!

만약에 바로 뒤에 있는 거 보다 내가

작으면 가려지므로 의미 없음

total = int(input())
buildings = []
for _ in range(total):
    buildings.append(int(input()))
stack = []
result = 0
for i in range(total):
    while stack and stack[-1] <= buildings[i]:
        stack.pop()
    result += len(stack)
    stack.append(buildings[i])
print(result)

오큰수

문제 = 앞에서 봤을 때 나보다 큰 가장 가까운 수 하나

방향 = →

입장을 바꿔서 자기가 오큰수가 될 수 있는지 확인

뒤에 있는 애들은 아직 오큰수를 못찾은 것! 만약 내가 걔네들보다 크면 바로 사수해야 오큰수 조건(가장 왼쪽에 있는 큰 수)를 만족

from collections import deque
total = int(input())
num = list(map(int, input().split()))
que = deque()
answer =[-1] * total
for i in range(total):
    while que and num[que[-1]] < num[i]:
            answer[que.pop()] = num[i]
    que.append(i)
print(" ".join(map(str, answer)))

탑 빌딩 옥상 관리 오큰수

문제	뒤에서 봤을 때 나보다 큰 수 하나	앞에서 봤을 때 나보다 작은 수 전체	앞에서 봤을 때 나보다 큰 가장 가까운 수 하나
방향	← (뒤)	→ (앞)	→ (앞)
기준	큰	작은	큰
선택 개수	1개	집합(수)	1개
입장	내가 레이저 누구한테 쏘는지(능동)	내가 선택될 수 있는지 (수동)	내가 오큰수가 되는지(수동)
for문 방향(하나씩 확인 방향)	0부터 (오름차순)	0부터(오름차순)	0부터(오름차순)