[백준 3015] 오아시스 재결합

 스택을 활용한 문제 중에서는 쉬운 축에 속하지는 않지만

 로직을 알고보면 금방 구현할 수 있는 문제이다.

우선 (1 ≤ N ≤ 500,000)

N 제한이 50만이기 때문에

for문으로 검사를 하면 25억번의 연산 => 25초가 걸리게 된다.

(시간초과)

그래서 간단하게 스택을 사용하도록 하면

대부분의 스택 연산에는 O(n)만에 연산이 가능하기 때문에

거의 1초 내로 풀 수 있게 된다. 

자세한 설명은 소스코드를 보면 이해가 쉽다.

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

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 2³¹ 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

예제 입력 1

7
2
4
1
2
2
5
1

예제 출력 1

10

소스코드

#include<iostream>
#include<stack>
 
using namespace std;
 
int main(void){
    int n;
    cin >> n;
    long long ans = 0;
    stack<pair<int, int> > st;                        // 키, 그 키를 가지는 인원 
    
    for(int i = 0; i < n; i++){
        int high;
        cin >> high;
        pair<int,int> p = make_pair(high, 1);                // 키, 인원 
        
        while(!st.empty()){
            if(st.top().first <= high){                // 자기보다 키가 큰 상대가 나타난 경우 
                ans += (long long)st.top().second;        // 우선은 1을 증가시킨다. (키가 같더라도 1 증가 => 서로 마주보기 가능) 
                if(st.top().first == high)            // 같다면 
                    p.second += st.top().second;        // 해당하는 인원을 증가시킨다. 
                st.pop();                    // 자기보다 키가 큰 상대가 나타났기 때문에, 더 이상은 무의미하다. pop 
            }
            else{
                if(!st.empty())                // 자기보다 키가 작은 상대가 나타남 (어깨 너머로 볼 수 있다)
                    ans += 1LL;                // 서로 마주보기 가능 
                break;                                     
            } 
        }
        st.push(p);                            // 첫 번째 사람, 자기보다 키가 더 작은 사람이 나타나면 push 
    }
    cout << ans;
    return 0;
} 

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.