우노
[Stack] 백준 2493번 “탑” Python 풀이 본문
문제 링크
풀이
- 모든 탑을 순서대로 탐색하며, 아래 조건에 따라 전처리한 뒤, 현재 탑의 정보를 (높이, 위치) 형식으로 Stack에 저장
- 현재 탐색하고 있는 탑의 높이가 Stack TOP의 높이보다 작다면, 현재 탐색하고 있는 탑의 레이저를 수신 받을 수 있는 탑의 위치를 저장
- 현재 탐색하고 있는 탑의 높이가 Stack TOP의 높이보다 크다면, Stack TOP 제거
코드
import sys
# 탑의 수
n = int(sys.stdin.readline())
# 탑의 높이
arr = [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 (arr[i] > stack[-1][0]):
# Stack TOP 제거
stack.pop()
# 현재 탐색하고 있는 탑의 높이가 Stack TOP의 높이보다 작다면
else:
# 현재 탐색하고 있는 탑의 레이저를 수신 받을 수 있는 탑의 위치를 저장
result[i] = stack[-1][1]
break
# 현재 탑의 정보를 Stack에 삽입
stack.append((arr[i], i))
# 결과 출력
for i in range(1, n+1):
print(result[i])
'Algorithm > Stack, Queue' 카테고리의 다른 글
[Stack] 백준 5397번 “키로거” Python 풀이 (0) | 2022.11.10 |
---|---|
[Stack] 백준 6198번 “옥상 정원 꾸미기” Python 풀이 (0) | 2022.11.05 |
[Stack] 백준 3986번 “좋은 단어” Python 풀이 (0) | 2022.11.02 |
[Stack] 백준 4949번 “균형잡힌 세상” Python 풀이 (0) | 2022.11.02 |
[Stack] 프로그래머스 “큰 수 만들기” Python 풀이 (0) | 2022.10.25 |
Comments