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

1. 문제 링크

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

 

2. 문제 접근

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

- 2 4 1 2 2 5 1이면 다음과 같다.

- (2,4) (4,1) (4,2) (4,2) (4,5) (1,2) (2,2) (2,5) (2,5) (5,1)

- 어떤 수(왼쪽 수) 입장에서 자신보다 큰 수가 등장했다는 것은 해당 인원들은 더 이상 쌍을 만들 수 없다. 

- 그 수를 기준으로 모두 pop()한다. pop()한 개수 만큼 더해준다. (pop된 수와 쌍을 만들 수 있음.)

- 오른쪽 수의 입장에서 왼쪽수가 자신보다 크다면, 적어도 왼쪽에 있는 수 중에는 쌍을 만들 수 있는건 1개다.

- 같은 수일때는 그 top에 있는 값이 만든 쌍의 개수 만큼 자신도 쌍을 만들 수 있다.

 

※ 정리

- 왼쪽 수 < 오른쪽 수 : 왼쪽 수는 더 이상 쌍을 만들 수 없으므로, pop() 처리. pop()한 수 만큼은 정답 증가

- 왼쪽 수 = 오른쪽 수 : top에 있는 값이 만든 쌍의 개수 만큼 자신도 쌍을 만들 수 있다. 

- 왼쪽 수 > 오른쪽 수 : 왼쪽 수가 나보다 크다면 오른쪽 수는 자신보다 이전에 나온 값과 쌍을 1개만 만들 수 있음.

 

- 위 로직을 근거로 Stack에 넣어보면 다음과 같이 동작한다.

① 비어있을때는 그냥 바로 넣어준다.

② stack에 있는 값이 작을땐 해당 값을 빼낸다. (1개이므로, 값 1증가)

③ stack에 있는 값이 더 크면, 해당 값이 만들 수 있는 쌍의 수를 1로 만든다.

④ stack에 있는 값과 현재 값이 같으면, 해당 값이 만들 수 있는 쌍 +1개 만큼 만들 수 있다.

 

3. 문제 풀이

- stack에 비어있는 경우엔 그냥 넣는다.

- stack에 있는 값을 기준으로, 작을때, 클때, 같을때를 구분해서 처리한다.

- 이 문제를 풀때 스택을 pair<int, int> 형태로 만들어서 해당 값과 함께 쌍을 만들 수 있는 개수를 같이 넣어준다.

- 쌍을 만들 수 있는 개수를 함께 넣어서 처리한다.

 

4. 소스 코드(C++)

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
stack <pair<int, int>> stk;
int value[500005];
long long int answer = 0;
int main(void)
{
	int n;
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> value[i];
	}
	for (int i = 1; i <= n; i++)
	{
		int temp = 0;
		while (!stk.empty() && stk.top().first < value[i]) // 스택에 있는 값보다 자신이 더 크면, 해당 인원들은 더 이상 쌍을 만들 수 없고, 그 값과 자신은 쌍을 만들 수 있음.
		{
			stk.pop();
			answer++;
		}
		if(!stk.empty() && stk.top().first == value[i]) // 만약 top에 같은 값이 있는 경우, 그 top에 있는 값이 만든 쌍의 개수(temp)만큼 쌍을 만들 수 있음. 거기에 자기 자신값을 더함.
		{
			temp = stk.top().second + 1;
			answer += temp;
		}
		else if (!stk.empty() && stk.top().first > value[i]) // 나보다 큰 값이 이미 등장했다면, 내 이전값중에 쌍을 만들 수 있는건 1개 값. 
		{
			temp = 1;
			answer += temp;
		}
		stk.push({ value[i], temp });
	}
	cout << answer;
}