반응형
2493번: 탑
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1
www.acmicpc.net
풀이
- 탑의 높이가 주어지고 , 왼쪽의 탑부터 왼쪽으로 레이저를 쏘아 그 레이저를 맞는 탑의 번호를 모두 구하는 문제다.
- 이 문제 역시 스택을 이용하면 편하다.
- 비슷한 문제로는 17298번 : 오큰수 가 있다.
알고리즘 - Python / 백준 - 17298번 : 오큰수 (tistory.com)
알고리즘 - Python / 백준 - 17298번 : 오큰수
17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net..
ddggblog.tistory.com
- 푸는 방법 역시 비슷하다.
- 탑의 높이 리스트를 역순으로 읽으며 다음 과정을 반복한다.
- 1. 다음 탑이 스택의 TOP 보다 높거나 같다면 , POP하고 그 탑의 레이저가 송신한 탑 (다음 탑)을 기록한다.
- 2. 만약 스택의 TOP 보다 작다면 , 스택의 맨 위에 그 탑을 추가하고 while 문을 break 한다.
- 1번 과정은 stack이 빌 때 까지 진행한다.
- 스택을 활용하는 방식이 오큰수 문제와 상당히 유사하고 흡사한 문제다.
import sys
n = int(sys.stdin.readline())
s = list(map(int , sys.stdin.readline().split(" ")))
stack = [[s[-1],n-1]]
ans = [0 for i in range(n)]
for i in range(len(s)-2,-1,-1):
check = True
while stack:
if stack[-1][0] <= s[i]:
pp = stack.pop(-1)
ans[pp[1]] = i + 1
else:
stack.append([s[i],i])
check = False
break
if check:
stack.append([s[i], i])
for i in range(0,len(ans)-1):
print(ans[i],end=" ")
print(ans[len(ans)-1])
반응형