# [Platinum V] 오아시스 재결합 [문제 링크](https://www.acmicpc.net/problem/3015) ## 문제 설명 <p>오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.</p> <p>이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.</p> <p>두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.</p> <p>줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)</p> <p>둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 2³¹ 나노미터 보다 작다.</p> <p>사람들이 서 있는 순서대로 입력이 주어진다.</p> ## 출력 <p>서로 볼 수 있는 쌍의 수를 출력한다.</p> ## 풀이 #### 스택에 비오름차순으로 저장하면서, 각 수가 등장한 횟수를 세면 된다. 비오름차순으로 저장하기 위해 pop하는 값들의 수만큼 cnt를 증가시킨다. 이 때에 스택에서 pop하는 값들은 모두 cur을 마지막으로 볼 수 있는 원소이다. 그리고 스택에서의 맨 위 값이 자신과 같을 수가 있기에 자신의 등장 횟수만큼 cnt를 증가시키고, 스택에서 자신보다 큰 수가 있을 경우 1번은 볼 수 있기에 cnt를 1 증가시킨다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; long long total=0; map<int, int> cnt; stack<int> stk; while(n--) { int cur; cin >> cur; while(!stk.empty() && stk.top()<cur) { int top = stk.top(); stk.pop(); total++; cnt[top]--; } total += min((int)stk.size(), cnt[cur]+1); // 7 7 5 5 뒤에 5를 넣는 경우 7 5 5 를 볼 수 있음. cnt[cur]++; stk.push(cur); } cout << total; } ```