[알고리즘] 백준 3015 오아시스 재결합 // 스택 심화

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

* 풀이

• stack은 그림을 그려놓고 <--- 방향으로 하나씩 탐색하면된다.
• 크게 3가지경우로 생각하라.
• 오름차순
  • 나보다 작은것들과 1쌍, pop

• 내림차순
  • 위에서 나보다 작은것은 걸러졌음, stack에 원소가 있다면, 무조건 나보다 큰것이 보장. 
  • 나보다 큰애와 1쌍을 이룬다.

 

오름차순, 내림차순을 고려한 코드

• 같은경우를 추가로 생각해야한다.
  • pop은 하되, cnt(//현재 사람의 연속 카운트)를 저장해놓는 idea
  • 같은거 뒤에 작은게옴 -> 정답 1쌍 추가 (위와동일) , cnt=1로 리셋
  • 같은거 뒤에 큰게옴 -> 이전 막대기의 cnt를 더해줘야함, cnt=1로 리셋
  • 같은거 뒤에 같은게옴 -> 현재cnt를 이전 막대기의 cnt +1로 갱신, 스택에넣기

• cnt 시작을 1로하고, 오름차순일때 ret+1 하는대신 ret+직전cnt 하면 일반화 된다.
• long long을 써야하는이유
  • 50만개의 모두 같은키가 오는경우 때문

 

 

* 최종코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, ret, arr[500000+4];

// < 키, 연속된 같은키 카운팅 >
stack<pair<ll,ll>> stk; // 최악 50만개 다같은키인경우) n(n-1)/2

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);

   cin>>n;
   for(int i=0;i<n;++i) {
      cin>>arr[i];
   }
   
   for(int i=0;i<n;++i) {
      int cnt=1; //현재 사람의 연속 카운트 초기값 = 1

      // 오름차순인경우
      while(stk.size() && stk.top().first <= arr[i]) {
         ret+=stk.top().second; // 누적된 카운트들 더하기
         //같은경우 카운팅해주기
         if(stk.top().first == arr[i]) {
            cnt = stk.top().second+1;
         }
         else {
            cnt=1; // 다른키인경우 카운트 리셋
         }
         stk.pop();
      }
      // 내림차순인경우, 나보다 더큰사람이 있다는뜻 -> 1쌍추가
      if(stk.size()) ret++; 
      stk.push({arr[i],cnt});
   }

   cout<<ret;
  
  
   return 0;
}