오아시스 재결합

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

 

<소스 코드>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
typedef struct {
    // 키
    int height;
    // 같은 키를 가진 사람 수
    int num;
}info;
 
info stack[600000] = { 0 };
int idx = -1;
 
void push(info value) {
    stack[++idx] = value;
}
 
info pop() {
    return stack[idx--];
}
 
int is_empty() {
    return (idx == -1);
}
 
info top() {
    return stack[idx];
}
 
int size() {
    return idx;
}
 
int main() {
    int people_num;
    scanf("%d", &people_num);
 
    int now, cnt_same_height = 0;
    long long  cnt_pair = 0;
 
    for (int i = 0; i < people_num; ++i) {
        scanf("%d", &now);
 
        cnt_same_height = 1;
        
        // stack을 이용해 오른쪽에서 왼쪽으로 비교
        while (!is_empty() && top().height < now) {
            cnt_pair += top().num;
            pop();
        }
 
        // 한번만 한다.
        if (!is_empty()) {
            // now와 키가 같다면 
            if (top().height == now) {
                // 같은 키를 갖는 사람과 모두 쌍을 지을 수 있음
                cnt_pair += top().num;
              
                cnt_same_height = (top().num + 1);
 
                // stack에 남아있다는 것은
                // now보다 키가 큰 사람도 있다는 뜻
                // ++cnt_pair 가능
                if (size() > 0)
                    ++cnt_pair;
 
                pop();
            }
            // now보다 키가 크다면
            else {
                ++cnt_pair;
            }
        }
 
        info tmp = { now, cnt_same_height };
        push(tmp);
    }
 
    printf("%lld\n", cnt_pair);
    return 0;
}