백준3015 오아시스 재결합

작성일 | In

문제 링크

  • http://icpc.me/3015

문제 출처

  • Croatian Olympiad in Informatics 2007 1번

사용 알고리즘

  • 스택

시간복잡도

  • O(n)

풀이

이 문제의 naive한 풀이는 O(n2)이지만, n제한이 최대 5e5이기 때문에 O(nlogn)이나 그보다 더 빠른 알고리즘을 생각해내야 합니다.

이 문제는 O(n)에 해결이 가능합니다. 방법을 알아봅시다. 스택을 사용할건데, 스택에 있는 원소들은 단조 감소 혹은 순감소 상태를 유지하도록 해야합니다.
이 글에서는 순감소 상태를 선택하겠습니다.

스택에는 pair<long long, long long> 타입의 데이터가 들어갑니다.
first에는 키, second에는 동일한 키를 갖고 있는 사람의 수가 저장이 됩니다.
first의 값이 순감소하는 상태를 유지하게 할겁니다. 그리고, 중복되는 값이 없게 할겁니다.
이렇게 하기 위해서는, 현재 값보다 스택의 top에 있는 값이 더 작거나 같으면 pop를 해줘야 합니다.

순감소 상태를 유지하게 된다면 몇 가지 사실을 알 수 있습니다.

  1. 스택 안에 있는 사람은 나중에 들어올 사람들이 볼 가능성이 있는 사람입니다.
  2. 이미 스택에서 pop된 사람은 나중에 들어오는 사람들이 절대 볼 수 없는 사람입니다.

이 사실을 이용해서 최적화를 할 수 있습니다.

조금 더 자세히 설명해봅시다.
현재 사람의 키 now와 스택의 top 값을 비교했을 때 top보다 now가 크다면 now보다 나중에 들어오는 사람은 절대로 top을 볼 수 없습니다. 그러므로 정답을 1 증가시킨 후 pop을 합니다.
이 행위를 top보다 작은 now가 나올 때까지 반복합니다.
스택에 now를 삽입해줍니다. 이 때, 스택이 비어있지 않으면 top이 now를 볼 수 있으므로 정답을 1 증가시킵니다.

위 방법은 중복된 값을 고려하지 않은 풀이이므로 때문에 틀립니다.
위에서 언급했듯이 pair의 second값은 중복되는 원소의 개수를 의미합니다.
now가 top보다 큰 경우에도 pop을 하지만, 같은 경우에도 pop을 합니다.
pop을 할 때는 1이 아닌 top의 second값만큼 정답을 증가시킵니다.
now와 top이 같은 경우에는 중복을 카운팅하는 변수를 만든 뒤 증가시키면 쉽게 처리 가능합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

void solve(int n){
	vector<ll> v(n);
	stack<p> s;
	for(int i=0; i<n; i++) cin >> v[i];
	ll ans = 0;

	for (int i=0; i<n; i++){
		int nu = 1;
        while(!s.empty() && s.top().first <= v[i]){
        	if(s.top().first == v[i]){
        		ans += s.top().second;
        		nu = s.top().second+1;
        		s.pop();
			}else{
				ans += s.top().second;
				s.pop(); nu = 1;
			}
		}

		if(!s.empty()) ans++;
		s.push({v[i], nu});
    }
	cout << ans;
}

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