백준 3015 오아시스 재결합 c++

[문제 링크]

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

[입출력 예]

입력	출력
7 2 3 1 2 2 5 1	10

[1차시도 - 실패]

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define X first
#define Y second

ll a[500000];

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

    ll answer=0;

    int n;
    cin>>n;
    stack <pair<ll,int>> s;
    pair<ll,int>max_pair ={(ll)INT_MAX +1,n};
    s.push(max_pair);

    //배열에 대입.
    for (int i=0; i<n; i++){
        cin>>a[i];
    }

    //반복문으로 오큰수처럼 풀이
    for (int i=n-1; i>=0; i--){

        // stack의 탑보다 큰 경우 -> top보다 요소가 작을때까지  top 빼기.
        if (s.top().X<a[i]){

            while(s.top().X < a[i]){
                s.pop();
                answer+=1;
            }
                if (s.top().Y!=n)answer+=1;
                s.push({a[i],i});

        }
        // stack의 탑보다 작은 경우
        else if (s.top().X>a[i]){

            s.push({a[i],i});
            if (i != n-1)answer+=1;
        }
        else {
          int tmpIdx;
          while(s.top().X==a[i]){
            tmpIdx=s.top().Y;
            s.pop();
          }
          answer+=tmpIdx-i;
          if (s.top().Y!=n) answer+=1;
          s.push({a[i],tmpIdx});
        }
    }

    cout<<answer;
    return 0;
}

// 이런 풀이로 풀 수가 없다.
// 이 풀이는 인덱스만 가지고 푸는 건데, 그렇게 푼다는 건 스택 안에 전조증가 수열로 남긴다는 것이다.
// 근데 그렇게 풀면 똑같은 키가 여러 번 나올 때 하나하나 다 세주기가 어렵게 된다.
// 그래서 몇번 반복되는지를 반드시 변수로 세서 넣어줘야 한다...

[소스코드]

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  stack<pair<int, int>> S;
  long long ans = 0;
  while (n--) {
    int h;
    cin >> h;
    int cnt = 1;
    while (!S.empty() && S.top().X <= h) {
      ans += S.top().Y;
      if (S.top().X == h) cnt += S.top().Y;
      S.pop();
    }
    if (!S.empty()) ans++;
    S.push({h, cnt});
  }
  cout << ans;
}

// [문제 해설]
// 1. 스택에는 이전까지의 키가 내림차순으로 쌓이게 된다.
// 2. 스택에 아무것도 없는 상황에서 새로운 데이터를 만난 경우, 스택에 데이터와 기본카운트 1을 넣는다.
// 3. 새롭게 만난 데이터가 스택의 top보다 크거나 같은 경우, stack의 top의 cnt를 더한다.
// 4. cnt는 해당 키를 가진 인물이 스택 속에 연속적으로 몇명이나 있는가.. 를 의미하는 것과 같다.
// 5. 새롭게 만난 데이터가 스택의 top보다 크다면, 그 데이터보다 큰 top이 나올 때까지 pop을 수행한다.
// 6. 그런데 이때, 새롭게 만난 데이터(h)와 stack의 탑이 같다면, 카운트를 올려줘서 새로운 데이터에 해당하는 값이 연속몇번인지 센다.
// 7. 뽑다 보면 경우의 수는 2가지로 나뉘는데, 끝가지 스택을 비워버리거나, 스택의 어떤 값에 막히는 경우일 것이다.
// 8. 만약 어떤 값에 막히는 경우라면(not empty) 그 사람을 볼 수 있는 상황이므로 ans에 하나 값을 더한다.
// 9. 끝가지 다 뽑았으면 끝까지 다 본 것이므로 ans를 조작하지 않는다.
// 10. 현재 해당하는 h값을 연속하는 회수 cnt와 함께 스택에 넣는다.

[출처]

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/solutions/3015.cpp