[BOJ 17638 // C++] Separator

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17638번 문제인 Separator이다.
문제는 아래 링크를 확인하자.

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

17638번: Separator

기존 수열에 새로운 항을 하나 추가할 때 separator의 개수가 어떻게 변화하는지를 관찰하는 것으로 문제를 해결할 수 있다.

 

1) 새로 추가되는 수가 separator인가?

정의에 따라, 기존에 등장한 모든 수보다 새로 추가되는 수가 크다면 이 수는 새로운 separator가 된다. 만약 기존에 등장한 수중 새로 추가되는 수보다 작거나 같은 수가 존재한다면 정의에 따라 새로 추가되는 수는 separator이 아니게 된다.

 

2) 기존 separator가 더이상 separator가 아니게 될 조건

조건 1)은 항상 만족하고 있으므로 기존 separator가 더이상 separator가 아니려면 기존 수보다 작거나 같은 수가 새로 추가되어야한다. 즉, 기존 separator이었던 수들 중 새로 추가되는 수보다 작거나 같은 수들은 더 이상 separator가 아니게 된다.

 

3) 기존에 separator가 아니던 수가 separator이 될 조건

불가능하다. 기존에 separator가 아니던 수는 새로 추가되는 단계에서 1)을 만족 못했거나 나중 단계에서 그 수의 오른쪽에 자신보다 작은 수가 등장한 경우 뿐이기 때문이다.

 

이중 2)를 빠르게 처리하기 위해 priority queue를 이용할 수 있다. 위의 아이디어를 이용해 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> pq;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int s = 0;

	int mx = -1;
	int N; cin >> N;
	while (N--) {
		int x; cin >> x;
		s = (s + x) % 1000000000;
		
		while (!pq.empty() && pq.top() >= s) pq.pop();
		
		if (mx < s) {
			mx = s;
			pq.push(s);
		}

		cout << (s = pq.size()) << '\n';
	}
}