[BAEKJOON] 3015 오아시스 재결합 (C++)

 

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

3015번: 오아시스 재결합

 

바킹독 알고리즘 문제집에서 스택 파트 응용문제로 있던 문제이다.

그리고 처음으로 풀어본 플레티넘 난이도 문제

그리고 나는 오아시스 노래를 좋아한다.

 

문제

서로 다른 키의 사람들이 한 줄로 서있을 때, 서로 마주볼 수 있는 쌍의 개수를 세는 문제

O(n^2)에는 쉽게 풀 수 있겠지만 그러면 시간초과가 날 것이다. 

 

스택 문제를 계속 풀다보니까 문제의 큰 틀이 좀 비슷한 것 같다.

뭐가 한 줄로 서있을 때 활용하기 좋은 자료구조이다.

 

풀이

마주볼 수 있는 조건은 두 사람 A, B 사이에 A와 B보다 큰 사람이 한 명도 존재하지 않는 것이다.

주어진 사람들의 키를 처음부터 확인한다. 그리고 본인보다 앞에 있는 사람과 마주칠 수 있는지 확인한다.

(쌍의 개수를 세는 것이므로 뒤에있는 사람과 마주치는 경우는 뒤에 있는 사람을 확인할 때 카운트된다.)

 

처리해야하는 케이스는 크게 3가지이다.

1. 자기보다 큰 경우

2. 작은 경우

3. 같은 경우

 

마주칠 수 있는 쌍을 확인 하는 사람을 A, 앞에 서있는 불특정 사람을 B라고 가정한다.

 

1. 앞에 서있는 사람(B)이 자기(A)보다 큰 경우

둘 사이에 A보다 큰 누군가가 없다면 마주볼 수 있다. 

즉 앞에 서있는 사람 중 A보다 큰 사람이 여러명 있더라도, 가장 가까이 있는 사람 한 명만 볼 수 있다.

 

2. 작은 경우

만약 스택 안에 내림차순으로 사람이 정렬된 상태라면 확인하는 사람보다 작은 사람들과는 마주칠 수 있음이 보장된다.

ex)

stack : 5 4 3 2 1      A 키 : 4

-> 4 3 2 1은 마주볼 수 있다.

하지만 4가 줄을 선 이후 뒤에 오는 사람들은 3 2 1을 볼 수 없다. (4가 가로막고 있기 때문)

따라서 3 2 1은 stack에서 제거한다. -> 이 작업을 반복한다면 stack내부의 값은 내림차순임을 보장한다.

1번에 의해 5가 카운트 되므로 4가 마주볼 수 있는 사람은 5명이다.

 

3. 같은 경우

이 문제를 어렵게 만드는 부분이 이 요소라고 생각한다.

같은 경우는 더 앞에 있는 사람과 마주보는데 장애물로 작용하지 않는다.

A와 키가 같은 경우, 해당 사람의 개수를 기록하고 그 수만큼 다시 stack에 push해준다.

-> 이렇게 하니 시간 초과가 난다.

ex) 

1 1 1 1 1 과 같이 같은 키의 사람이 많아진다면, stack에서 뺐다가 다시 넣는 작업을 N^2만큼 해야하는 경우가 발생한다.

따라서 나는 pair자료구조를 이용해서 키, 사람수의 쌍으로 값을 저장했다.

키가 같은 경우는 cnt값을 증가시키고, 증가된 cnt값으로 다시 stack에 push해줌으로써 시간초과를 해결하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define endl "\n"

using namespace std;

int N;
stack <pair<int,int>> stk;

void Solve() {
	cin >> N;
	int k, cnt=0;
	long long ans = 0;
	for (int i = 0; i < N; i++) {
		cin >> k;
		cnt = 1;
		while (!stk.empty() && stk.top().first <= k) {
			if (stk.top().first == k) cnt += stk.top().second;
			ans+=stk.top().second; stk.pop();
		}
		if (!stk.empty()) ans++;
		//cout << k << " " << ans << endl;
		stk.push({k,cnt});
	}
	cout << ans;
}


int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	Solve();
	return 0;
}