파이썬 백준 17608 막대기

import sys   input = sys.stdin.readline n = int(input()) l = [0 for i in range(n+1)] l[0] = 0 stack = [[0, 0]] for i in range(1, n+1) :     h = int(input())     if h >= l[i-1] :         while len(stack) > 0 and stack[-1][1] <= h :             del stack[-1]         stack.append([i, h])     else :         stack.append([i, h]) print(len(stack))

새로 체크하는 기둥의 높이 h가 [-1]보다 [-1]부터 h보다 낮은 기둥은 모두 더이상 안보이니 날린다.

낮다면 [-1]이 계속 보이니 새 기둥을 스택에 넣는다.

 

생각해보면 스택을 안쓰는게 덜 복잡하다.

처음부터 끝까지 리스트에 넣고, 오른쪽부터 출발해서 현재의 max보다 클때만 count를 더하면

길이 n의 리스트를 저장해서 한번만 갔다 돌아와도 계산이 끝난다.

 

대신 스택을 쓰면 길이n의 리스트를 쓸 필요가 없으니 메모리의 차이가 있을 것이다.

스택이든 큐든 그냥 풀어도 되지만 자원을 아끼기 위해 구조의 특수성을 이용하는데에 목적이 있는 것 같다.