[알고리즘 문제풀이] [파이썬] 백준 #2493 탑

d·2023년 3월 14일
0

알고리즘문제풀이

목록 보기
1/6
post-thumbnail

백준 #2493 <탑> 문제 링크:www.acmicpc.net/problem/2493

문제

예제 입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다.
둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

5
6 9 5 7 4

예제 출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의
번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지
않으면 0을 출력한다.

0 0 2 2 4

코드

# 백준 2493
import sys
input = sys.stdin.readline

n = int(input().rstrip())
tower = list(map(int, sys.stdin.readline().split()))
stack = []
check = [0] * n

for i in range(n): # 탑을 하나씩 본다
    t = tower[i]
    while stack and tower[stack[-1]] < t: # 스택의 탑보다 현재 탑이
        stack.pop() # 크면 팝
    if stack: # 스택이 남았으면 
        check[i] = stack[-1] + 1 # 현재 탑의 신호를 받는 탑의 인덱스 체크
    stack.append(i) # 현재 탑의 인덱스 스택에 푸쉬

print(*check, sep=' ')

알고리즘 문제풀이 모음:

github.com/whwogur/BOJ

0개의 댓글