(3015) 오아시스 재결합

https://www.acmicpc.net/problem/3015

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 5번째

 

 

 

어떤 사람을 기준으로 나보다 키가 큰 사람이 나타나면 그 뒤의 사람은 절대 볼 수 없다.

지금 탐색하는 사람이 스택 안에 존재하는 사람보다 키가 크다면 존재하는 사람은 더 이상 내 뒤의 사람을 볼 수 없으므로 (검사할 필요가 없으므로) 스택에서 빼버리면 된다. 이때 스택 내부는 내림차순으로 이루어진다.

또한 키가 같은 사람이 있으므로 스택에 키와 사람수 두 가지 변수를 저장한다.

 

지금 탐색하는 사람은 스택 top의 사람과 비교하여 세 가지 경우로 나눌 수 있다.

1) 스택 내 사람이 더 작음: 그 사람과 나는 서로 볼 수 있으므로 사람 수만큼 ans에 값 추가, 그 사람은 더 이상 현재 사람 뒤의 사람을 못 보므로 스택에서 제거

2) 스택 내 사람과 같음: 서로 볼 수 있으며, 이후 사람에서 탐색할 때 앞 사람과 가능 여부를 공유하므로 사람수를 1 증가시킨다.

3) 스택 내 사람이 나보다 큼: 앞쪽 사람 중에서는 더 이상 현재 사람과 볼 수 있는 쌍이 없으므로 탐색 종료. 나보다 큰 사람과는 서로 볼 수 있으니 ans에 값을 1 추가한다.

 

 

 

#include <iostream>
#include <stack>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  long ans= 0;
  stack<pair<int,int>> s;
  
  cin >> n;
  
  while(n--){
    int h, cnt= 1;
    
    cin >> h;

    while(!s.empty()){
      if(s.top().first<h){
        ans+= s.top().second;
        cnt= 1;
        s.pop();
      }else if(s.top().first==h){
        ans+= s.top().second;
        cnt= s.top().second+1;
        s.pop();
      }else{
        ans++;
        
        break;
      }
    }
    
    s.push(make_pair(h, cnt));
  }
  
  cout << ans;
  
  return 0;
}