[Jungol] 정올 2538 PATRIK

출처: [Jungol] 정올 2538 PATRIK

Approach

Q) 중간에 자신들보다 큰 사람이 없는 경우 서로 마주볼 수 있는 한 쌍입니다.

A) 사람이 다음과 같이 서있을 때, [3 3 1] 양 끝에 위치한 『3』과 『1』은 서로를 볼 수 있을까?

     왼쪽 『3』 ≥ 중간 『3』 이지만 오른쪽 『1』 < 중간 『3』 이므로, 결과적으로 서로 볼 수 없습니다.

 

▶  [스택] Stack 이란? 

[스택] Stack 이란?

 Input 

4

3

3

1

1

 

 Output 

 4

- 첫번째 입력 Data는 Stack에 비교 데이터가 없으므로 push

   (스택이 비워져 있는 경우에는 입력 데이터 push)

- 입력 데이터 push 전에 스택이 비워져 있지 않은 경우

   → 입력데이터 보다 작은 값은 pop()

   → 입력데이터와 동일한 값은 pop() 하기 전에 등장 횟수를 누적.

        따라서, 스택에는 입력데이터 큰 값만 남겨둡니다. 동일한 키는 누적해서 스택에서 저장합니다.

   → 스택이 비워져 있지 않은 경우, 자신보다 큰 데이터가 적어도 한 개 존재하므로

        top()에 위치한 것만 입력데이터와 서로 볼 수 있으므로 남아 있는 개수와 상관없이 +1 처리

※ 스택에 저장되는 정보는 키와 동일한 키의 누적값입니다.

---

#include <stdio.h>
 
typedef long long LL;
const int MAX_N = 500000;
LL ans;
struct Stack {
    int height, cm;
} stack[MAX_N + 10];
int sp, data;
void push(Stack next) { stack[++sp] = next; }
Stack top() { return stack[sp]; }
void pop() { sp--; }
bool isEmpty() { return sp == 0; }
int size() { return sp; }
 
int main() {
    // freopen("input.txt", "r", stdin);
 
    int N; scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &data);
        Stack next = { data, 1 };
 
        while (!isEmpty()) {
            if (top().height > data)
                break;
 
            // 입력 데이터보다 작거나 같은 경우
            // (같은 값이 경우) 해당 데이터 누적
            if (top().height == data)
                next.cm += top().cm;
            ans += top().cm;
            pop();
        }
        if (!isEmpty()) {
            ans++;
        }
        push(next);
    }
    printf("%lld\n", ans);
}