정올 1141번: 불쾌한 날

문제

문제 바로가기> 정올 1141번: 불쾌한 날

JUNGOL

 

풀이

N이 최대 80,000이므로 각 소에 대해서 이중 for문을 돌면서 확인할 경우 시간초과가 발생한다.

내가 볼 수 있는 소의 수를 세는 것이 아니라, 나를 볼 수 있는 소의 수를 센다면, O(N)으로 문제를 해결할 수 있다.

다음과 같이 스택 안에 나(H[i])를 볼 수 있는 소들만 들어 있도록 유지하면 된다.

(1번 소가 3번 소를 볼 수 있고, 3번 소가 4번 소를 볼 수있으면, 1번 소는 4번 소를 볼 수있다.)

 

#include<iostream>
#include<stack>
#define MAX 80001
using namespace std;

int N;
int H[MAX];

void input(){
    cin >> N;
    for(int i=0; i<N; i++) cin >> H[i];
}

void solve(){
    long long ans = 0;

    stack<int> st;
    for(int i=0; i<N; i++){
        while(!st.empty() && st.top() <= H[i]) st.pop();
        ans += st.size();
        st.push(H[i]);
    }
    cout << ans;
}

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