[C++] 백준 3015번 오아시스 재결합

문제

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

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

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

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

입력

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

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

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

출력

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

풀이

만만해보이는 문제였지만 골드1답게 꽤나 헤맸었다. 키가 같은 사람이 계속 들어왔을때가 처리하기 까다로웠다.
해법은 pair로 키와 키가 같은 사람이 연속한 수를 묶는 것이다.
먼저 이전 사람보다 키가 큰 사람이 들어왔다면 이 사람보다 키가 작은 사람은 더 이상 결과에 영향을 미치지 못하기때문에 인원수 만큼 결과에 더하고 스택에서 제거해도 상관이 없다. 작은 사람들을 모두 지우고 나면 스택은 비어있거나 자신보다 더 큰 사람들만 남아 있을것이다.
바로 앞이 자신보다 크다면 결과에 1쌍이 추가된다.
바로 앞이 자신과 같다면 4 2 2 2와 2 2 2 2 같이 스택에 자신보다 큰 사람이 앞에 있는 경우와 없는 경우로 또 갈린다. 큰 사람이 있다면 자신과 키가 같은 사람들은 물론 키가 4인 사람도 볼 수 있기때문에 결과에 같은 키인 사람들의 수 + 1을 추가하고 아닌 경우에는 결과에 같은 키인 사람들의 수만 추가하면 된다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <stack>
#define endl '\n'

using namespace std;

int n,height;
long long ans;
stack<pair<int,int>> s;

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n;

  for (int i=0; i<n; i++){
    cin >> height;

      // 큰 키 
    while (!s.empty() && height > s.top().first){
      ans += s.top().second;
      s.pop();
    } 
    // 비어있음
    if (s.empty()) 
      s.push(make_pair(height,1));

    else{    
      // 같은 키
      if (s.top().first == height){
        int cur = s.top().second;
        s.pop();
        if (!s.empty()) ans++;
        
        ans += cur;
        s.push(make_pair(height,cur+1));
      }
      // 작은 키
      else{
        ans += 1;
        s.push(make_pair(height,1));
      }
    }
  }
  
  cout << ans;
}