문제링크:https://www.acmicpc.net/problem/2493
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
다루는 주제: 스택
import sys
# 탑의 수
N = int(sys.stdin.readline())
# 탑의 높이
tops = [0] + list(map(int, sys.stdin.readline().split()))
result = [0] * (N + 1)
stack = []
for i in range(1, N + 1):
# Stack에 탑의 정보가 남아있다면
while stack:
# 탑의 높이가 Stack TOP의 높이보다 크다면
if tops[i] > stack[-1][0]:
# Stack TOP 제거
stack.pop()
# 탑의 높이가 Stack TOP의 높이보다 작다면
else:
# 현재 탐색하고 있는 탑의 레이저를 수신 받을 수 있는 탑의 위치를 저장
result[i] = stack[-1][1]
break
# 탑을 Stack에 삽입
stack.append((tops[i], i))
# 결과 출력
for i in range(1, N + 1):
print(result[i], end=" ")
'Algorithm > 백준(파이썬)' 카테고리의 다른 글
백준 5904 파이썬(Python) 문제풀이 Moo (0) | 2023.04.20 |
---|---|
백준 2805 파이썬(Python) 문제풀이 나무자르기 (0) | 2023.04.19 |
백준 10830 파이썬(Python) 문제풀이 행렬제곱 (0) | 2023.04.17 |
백준 6549 파이썬(Python) 문제풀이 히스토그램에서 가장 큰 직사각형 (0) | 2023.04.17 |
백준 1629 파이썬(Python) 문제풀이 곱셈 (0) | 2023.04.16 |