(python) 백준 #2493 - [G5] 탑 : 스택

2493번: 탑

 

유의미한 탑만 남기자

유의미한 탑은 신호가 도달할 가능성이 있는 탑이다. 자기자신보다 큰 탑에 신호가 완전히 막힌 탑은 앞으로 무의미한 탑이된다. 그런 탑들을 제외하면서 정보를 가져가면 빠르게 탐색할 수 있다.

스택을 이용해서 관리할 수 있다. 앞에서부터 탐색을 진행하면서 스택의 가장 위에 있는 탑보다 현재 탑이 더 높은 경우 스택에 있는 탑은 무의미한 탑이 되므로 pop해서 모두 제거한 뒤 현재 탑을 스택에 추가한다.

 

시간복잡도

시간복잡도는 O(N)으로 대략 2N정도의 탐색으로 해결할 수 있다고 생각된다.

 

코드

'''
Title   : 탑
Link    : https://www.acmicpc.net/problem/2493
Level   : G5
Problem : 모든 탑의 꼭대기에서 왼쪽으로 신호를 보낸다. 신호를 받는 탑의 위치를 출력한다.
Type    : 스택
Idea    : 앞에서부터 검사를 진행한다. 스택에는 부딪힐 수 있는 탑들만 남긴다.
          스택의 원소가 검사할 탑보다 낮다면 pop한다.
          새 원소를 스택에 추가한다.
TC      : O(N). 약 2N이라고 생각된다.
'''

import sys


def solution(input) :
    N = int(input().rstrip())
    towers = list(map(int, input().split()))
    answer = [0]*N
    stack = [0]

    for i in range(1,N) :
        while stack and towers[stack[-1]] < towers[i] :
            del stack[-1]
        if stack : answer[i] = stack[-1]+1
        stack.append(i)
    
    #print(*answer)
    print(" ".join(map(str, answer)))

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac