백준 3015번 - 오아시스 재결합(C++)

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

 

Greedy 문제처럼 생겨서 그리디로 접근하려 했지만 N의 개수를 확인했을 때 반복문 안에서 다시 반복문이 실행되는 순간 시간 초과가 발생할 것임을 직감했다. 그래서 결국 문제 분류를 보니 stack 을 확인했다.

들어오는 숫자에 따라 스택을 사용해 f(x)를 구성하면 N번의 Stack Push로 O(N) 에 문제를 해결할 수 있다.

 

문제는 3가지 경우로 나눌 수 있다. 

 

이번에 들어온 사람의 키가 직전 사람보다 ~

1. 작은 경우

2. 같은 경우

3. 큰 경우

 

1번 직전 사람보다 작은 경우를 생각해보자. 

 

543 2 

 

현재 stack.top() = 3 이며 3은 자기 직전 4, 이후 2와 마주볼 수 있다.

 

2번 같은 경우를 생각해보자.

 

543 3

 

현재 stack.top() = 3 이며 3은 자기 직전 4, 이후 3과 마주볼 수 있다. 그리고 같은 숫자이기 때문에 같은 키는 간단하게 몇개가 있는지 표시하여 사용할 수 있다. 그리고 같은 키들 3 3 3 이어도 서로가 마주볼 수 있다는 것을 유의하자.

 

543 6

 

현재 stack.top() = 3 이며 3은 자기 직전 4, 이후 6과 마주볼 수 있다. 그리고 6의 다음으로 어떤 숫자가 오던 간에 6 이전의 사람들을 마주볼 수 없다. 모두 6보다 작기 때문이다. 즉, 모두 pop해버릴 수 있다. 그리고 6은 5, 4, 3 모두와 마주볼 수 있다.

 

정리하면 스택에는 결국 키가 큰 순서로 8 3 2 1 이런 식으로 들어오다가 지금 top보다 큰 숫자가 들어오면 키순서대로 정리되는 형태로 진행된다. 그러므로

 

지금 top이 현재 가장 작은 키라는 것이 보장되므로 만약 지금 들어온 사람의 키가 top보다 작다면 top과 마주보는 것만 생각하면 되므로 answer += 1 

 

그렇지 않다면 9 5 4 3 에서 6이 들어왔다면 6보다 작은 5, 4, 3은 모두 빠지면서 같은 키의 개수만큼 answer에 더해지게 되고 스택에는 9만 남는다, 스택에 뭔가 남아있다는 것은 지금 들어온 키보다 큰 키가 하나 이상 있다는 것이므로 9와 6의 페어를 지어줌으로 answer += 1을 또 해준다.

그러니까 같거나 크다면 스택을 정리하는 로직이 추가된다. 코드로 표현하면 다음과 같다.

 

#include <iostream>
#include <stack>
#include <vector>
#define ll long long

using namespace std;

vector<ll> s;

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

	s = vector<ll>(N);

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

	stack<pair<ll, int>> stk;
	ll answer = 0;
	for(int i = 0; i < N; i++){
		ll value = s[i];

		int same_cnt = 1;

		while(!stk.empty() && stk.top().first <= value){ // 벨류보다 작은 것들은 필요없다.
			answer += stk.top().second;
            if(stk.top().first == value) same_cnt += stk.top().second;
			stk.pop();
		}

		if(!stk.empty()){ // 스택이 비어있지 않음
	    	answer++;	
		}

		stk.push({value, same_cnt});
	}

	cout << answer << '\n';
}