스택 - 백준 17298 (22.6.10)

사용자가 특정 차트를 고르면, 전 종목의 과거(10년) 차트들을 모두 탐색하여 가장 유사한 차트 10개를 골라 사용자에게 보여줍니다.

 

웹프로젝트 링크

비슷한 차트 검색기

 

 

 

스택이란

 

스택은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-In-First-Out) 자료구조이다.

백준 17298번 문제는 스택을 이용하여 풀 수 있다.
스택의 생성, 삽입, 삭제, 조회, 응용 등을 알아보자.

 

n = int(input())
seq = list(map(int, input().split()))
stk = [] # 스택 생성
ans = [-1] * n

for i in range(n): # 스택에 큰 수가 밑으로 가게 쌓는다
    while stk and seq[stk[-1]] < seq[i]: # 쌓을 수가 자리에 맞게 아래로 갈 때까지 작은 수들을 pop 해서 스택을 비운다
        ans[stk[-1]] = seq[i] # pop 한 자리는 쌓을 수가 오큰수가 된다.
        stk.pop() # 제거 - 조회만 할때는 stk[-1]
    stk.append(i) # 삽입

print(' '.join(map(str, ans)))