백준 3015번: 오아시스 재결합 C++ 문제 해결

 

오늘은 백준에서 스택 문제 중 오아시스 재결합에 대해서 설명해보겠습니다.

 

먼저 이 문제는 복잡한 알고리즘을 필요로 하지는 않습니다.

 

제가 해결한 방법은 2493번: 탑 문제를 보고 오시면 쉽게 이해하실 수 있을 것 같습니다.

 

간단히 설명드리면

1. 스택에 pair를 이용해 키와 키가 같은 사람의 수를 푸시
2. 입력된 숫자와 앞에 선 사람의 키를 비교할 때 작은 숫자가 입력된 것이 아니면 기존 정보 삭제(작은 숫자가 입력되면 더 이전 숫자는 마주 볼 수 없음)
3. 앞에 선 사람보다 키가 크거나 같으면 카운트 증가, 같을 경우에는 키가 같은 것을 나타내는 변수를 더해 스택에 푸시

좀 이해하기 어려울 수 있으니 코드를 분석 해보겠습니다.

#include <iostream>
#include <stack>
#define height first
#define equal second
using namespace std;

long long int n, num, result = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	stack<pair<long long int, long long int>> S;
	cin >> n;

	while (n--) {
		cin >> num;

		long cnt = 0;
		long equal_num = 0;

		while (!S.empty()) {
			if (num > S.top().height) {
				cnt += S.top().equal + 1;
				S.pop();
			}
			else if (num == S.top().height) {
				cnt += S.top().equal + 1;
				equal_num = S.top().equal + 1;
				S.pop();
			}
			else {
				break;
			}
		}
		if (!S.empty()) cnt++;
		S.push({ num, equal_num });
		result += cnt;

	}
	cout << result;

	return 0;
}

 

1. cnt 변수와 equal_num 변수는 각각의 입력마다 마주보는 사람의 수, 중복되는 키를 가진 사람의 수를 저장합니다.
2. 반복문 진행 중 num이 앞에 선 사람보다 크면 cnt를 추가하며 앞에 선 사람의 정보를 삭제합니다.
3. 같을 경우에는 똑같이 cnt를 추가하며 정보를 삭제하지만 키가 겹치기에 equal_num의 수도 추가합니다.
4. 작은 경우나 앞에 숫자가 없는 경우에는 앞에 선 사람 이전의 사람은 마주 볼 수 없어 패스합니다.
5. if (!S.empty()) cnt++;은 작은 수가 입력되었을 때 반복문을 빠져나왔을 때 숫자가 남아있다면 그 숫자를 볼 수 있기에 cnt를 증가 연산합니다.
6. 스택에 정보를 추가하고 result 변수에 쌍의 수를 더해줍니다.
7. cnt 변수나 equal_num 변수에 수를 더할 때 스택의 top의 equal 요소에 1을 더하는지 궁금할 것입니다. 이는 우리가 앞서 계산할 때 여러 명의 키가 겹치면 이미 정보를 삭제해버려 몇 명이 겹치는지 몰라 1명만 계산하게 됩니다. 이를 위해 equal 요소를 만들어놨기에 더해서 변수에 입력합니다. 키가 안겹쳤다면 0인 상태기에 크게 신경 쓸 것은 없습니다.