📁문제 설명
오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.
📁입력
첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.
📁출력
서로 볼 수 있는 쌍의 수를 출력한다.
📁입출력 예
입력
7
2
4
1
2
2
5
1
출력
10
📁풀이
import sys
n = int(sys.stdin.readline().strip())
stack = []
result = 0
for _ in range(n):
s = int(sys.stdin.readline().strip())
while stack and stack[-1][0] < s:
result += stack.pop()[1]
if not stack:
stack.append([s, 1])
continue
if stack and stack[-1][0] == s:
cnt = stack.pop()[1]
result += cnt
if stack:
result += 1
stack.append([s, cnt+1])
else:
stack.append([s, 1])
result += 1
print(result)처음에는 s값만 가지고 비교를 했었다. 역시나 실패ㅠㅠ 도무지 방법이 생각나지 않아 구글링을 해보니 키가 값은 사람을 계산하기 위해 cnt 값을 넣어줬다.
확실히 플레티넘 문제다 보니 문제가 복잡하다. 그래도 해설을 이해했다는 것에 의의를 둬야겠다.
