문제

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

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

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

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

입력

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

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

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

출력

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

풀이

문제 풀이 방향성:

1. 사람 수가 N이라 할때, 오름차 순으로 정렬된 경우 N-1
2. 사람 수가 N이라 할때, 내림차 순으로 정렬된 경우 N-1
3. 사람 수가 N이라 할때, 모두 값이 동일할 경우 N(N+1)/2
   
4. 사람 수가 N이라 할때, 양끝 점 A,B가 있고, A와B보다 크고 A와B 중간에 위치하고 있는 X의 값이 있다면, X값 이후에 값은 처리할 필요가 없다.

핵심 아이디어:

1. 현재 입력받은 키 X가 stack에 들어간 값들보다 크다면, 그 이후에 입력 되는 값은 처리할 필요가 없다.
2. 같은 값으로만 들어올 경우 최대 N(N+1)/2이 출력된다.

   N=500000 -> 500000*500001/2=125000250000

3. 입력받는 키 연속적으로 중복될 경우, cnt 변수를 통해 키를 카운트하고 누적하여 stack에 저장한다.

입력:

1) N을 입력받아 줄에 서 있는 사람의 수를 저장한다.
2) 각 사람의 키 x를 입력받는다.

스택 사용:

1) 스택 strk는 (키, 볼 수 있는 쌍 수)의 형태로 사람의 키와 그 키를 가진 사람 수를 저장한다.
2) 스택의 최상단 사람은 마지막에 입력된 사람의 정보를 나타낸다.

볼 수 있는 쌍 계산:

현재 입력받은 키 x에 대해, 스택을 반복하면서 다음을 수행한다:
1) 스택의 최상단 사람이 현재 사람 x보다 크면 더 이상 비교할 필요가 없으므로 반복을 종료한다.
2) 스택의 최상단 사람이 x보다 작거나 같으면:

• ret에 스택의 최상단 사람의 볼 수 있는 쌍 수를 더한다.
• 만약 최상단 사람이 x와 같은 키를 가지고 있다면, count를 업데이트한다. 이는 같은 키를 가진 사람의 수를 누적하기 위한 것이다.
• 최상단 사람이 x보다 작다면 count를 1로 초기화한다.

3) 스택에서 최상단 요소를 제거한다.

4) 남아 있는 사람 처리:
스택이 비어 있지 않다면, 현재 사람 x보다 키가 큰 마지막 사람과의 쌍을 하나 더 추가한다.

결과 출력:

1. 최종적으로 ret에 저장된 볼 수 있는 쌍의 총 수를 출력

---

C/C++ 코드

#include <iostream>
#include<vector>
#include<stack>
using namespace std;
int N;
stack <pair<int, unsigned long long>> strk;
unsigned long long ret = 0;
int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int x;
		cin >> x;
		int count = 1;
		while (!strk.empty()) {
			if (strk.top().first > x) {
				break;
			}
			ret += strk.top().second;
			if (strk.top().first == x) {
				count = strk.top().second + 1;
			}
			else {
				count = 1;
			}
			strk.pop();
		}
		if (!strk.empty()) ret += 1;
		strk.push({ x,count });
	}
	cout << ret;
	return 0;
}