[BOJ][C++] 3051번 오아시스 재결합

안녕하세요.

오늘은 백준 3015번: 오아시스 재결합(링크)  문제를 풀어보려고 합니다.

 

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.
이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.
줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)
둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 2^31 나노미터 보다 작다.
사람들이 서 있는 순서대로 입력이 주어진다.

 

출력

서로 볼 수 있는 쌍의 수를 출력한다.

 

예제 입력

7
2
4
1
2
2
5
1

 

예제 출력

10

 

제한

시간 제한: 1초

메모리 제한: 256MB

 

---

풀이

다른 스택 응용 문제와 비슷하게, 스택 안에 있는 값들을 일정 조건에 따라 유지시키면서 진행해나가는 방식이다.

정확한 용어는 모노톤 스택/큐/덱 이라고 불린다.

 

풀이 과정은 다음과 같다.

 

가정: 스택의 있는 수열은 감소/유지되는 수열이다.

0. 입력받은 배열을 앞에서부터 검사한다.

1. 스택이 비어 있는 경우 값 x을 push한다.

2. 스택의 top() < x인 경우

-> x 뒤에 오는 값들은 top()하고 볼 수가 없다. 따라서 top() <-> x인 경우만 계산해준다.

3. 스택의 top() == x인 경우

-> 처음 세운 가정에따라, top() 이전에 쌓인 수들은 모두 x보다 크거나 같다.

-> 즉, x는 x보다 큰 값이 나오는 순간까지의 사람하고 서로 볼 수가 있다.

4. 스택의 top() > x인 경우

-> x는 top()하고만 서로 볼 수가 있으므로, 해당 경우만 계산해준다.

 

이렇게 과정을 정리해서 구현했었는데, 시간 초과가 나왔었다.

이유는 top()==x인 경우를 셀 때 스택에서 뺐다가 다시 넣는 과정으로 구현했었기 때문이다.

// 비효율적 코드
if (s.top() <= x) {
    stack<int> tmp;
    while (!s.empty() && s.top() <= x) {
        if (s.top() == x) {
            tmp.push(s.top());
        }
        ans++;
        s.pop();
    }
    if (!s.empty()) {
        ans++;
    }
    while (!tmp.empty()) {
        s.push(tmp.top());
        tmp.pop();
    }
    s.push(x);
}

 

따라서, 현재 x라는 수가 몇개 있는지 기록하기 위해 map을 사용해서 다시 수정했고 이후 정답을 맞췄다.

map<int, int> cnt; // 숫자 개수를 세기 위한 map
//...
if (s.top() <= x) {
	while (!s.empty() && s.top() < x) {
		ans++;
		cnt[s.top()]--;
		s.pop();
	}
	ans += cnt[x];
	if(cnt[x]-s.size()>0) {
		ans++;
	}
	s.push(x);
	cnt[x]++;
}
///...

 

정답

#include <iostream>
#include <stack>
#include <map>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin.tie(NULL);
	int n; cin >> n;
	ll ans = 0;
	stack<int> s;
	map<int, int> cnt;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		if (s.empty()) {
			s.push(x);
			cnt[x]++;
			continue;
		}
		if (s.top() <= x) {
			while (!s.empty() && s.top() < x) {
				ans++;
				cnt[s.top()]--;
				s.pop();
			}
			ans += cnt[x];
			if(cnt[x]-s.size()>0) {
				ans++;
			}
			s.push(x);
			cnt[x]++;
		}
		else {
			ans++;
			s.push(x);
			cnt[x]++;
		}
	}
	cout << ans;
}

---

이렇게 해서 백준  3015번 오아시스 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!