[Python] 백준 - 3015 오아시스 재결합

 

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

 

 

문제해결방법- 서칭 참고

 

이 문제는 예전에 봤는데도, 떠올리기가 어렵다.

 

 

d[i]가 왼쪽에서 볼 수 있는 사람을 카운팅하는 개념. 

import sys
input = sys.stdin.readline

n = int(input())
d = [0]+[int(input()) for _ in range(n)]
stack = [[0, 0]]
ans = [0 for _ in range(n+1)]

for i in range(1, n+1):
	cnt = 1
	while stack and 0 < stack[-1][0] <= d[i]:
		pop, cnt = stack.pop()
		if 0 < pop < d[i]:
			ans[i] += cnt
			cnt = 1
		elif pop == d[i]:
			ans[i] += cnt
			cnt += 1
	if stack and stack[-1][0] != 0:
		ans[i] += 1
	stack.append([d[i], cnt])
print(sum(ans))