[C++] 백준 17162번: 가희의 수열놀이 (Small)

문제 링크

17162번: 가희의 수열놀이 (Small)

문제 요약

다음의 쿼리들을 수행해야 한다.
1 num : 수열 arr의 맨 뒤에 num을 추가한다. ($1$ ≤ $num$ ≤ $2^{31-1}$)
2 : 수열 arr의 맨 뒤에 있는 원소를 제거한다. 만약 arr이 비어있으면 무시한다.
3 : 수열 arr의 맨 뒤에서부터 수들을 선택해서 이들을 mod로 나누었을 때 나머지가 0, ... , mod-1인 경우가 각각 한 번 이상 나타나기 위해 골라야 할 수의 최솟값을 출력한다.

접근 방법

mod가 최대 100이기 때문에 100개의 벡터를 이용해줍니다.

for문을 Q번 돌리면서 각 쿼리를 다음과 같이 처리해주면 됩니다.

1. num % mod번째 벡터에게 현재 반복문의 i를 삽입한다.
2. 각 벡터의 back()을 비교하고, 이 중에 최댓값을 삭제해준다. 만약 모든 벡터가 empty()인 경우에는 무시한다.
3. 모든 벡터 중에 하나라도 empty()인 경우에는 -1을 출력한다. 그렇지 않은 경우 각 벡터의 back() 중에 최솟값을 찾는다. 그리고 모든 벡터에 대해 lower_bound()를 이용해서 back()의 최솟값보다 큰 원소의 수를 구한다.

AC는 받긴 했는데, 다른 분들 풀이보다는 100ms 정도 더 느리게 나왔습니다. 코드도 지저분하게 나온거 같아서 노력이 더 필요할거 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

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

	int q, mod;
	cin >> q >> mod;

	vector<int> v[100];
	for (int i = 0; i < q; i++)
	{
		int query;
		cin >> query;

		if (query == 1)
		{
			int num;
			cin >> num;
			v[num % mod].push_back(i);
		}
		else if (query == 2)
		{
			int max = -1, pos = -1;
			for (int j = 0; j < mod; j++)
			{
				if (v[j].empty())
					continue;
				if (v[j].back() > max)
				{
					max = v[j].back();
					pos = j;
				}
			}

			if (pos != -1)
				v[pos].pop_back();
		}
		else
		{
			bool flag = false;
			int min = INT_MAX;
			for (int j = 0; j < mod; j++)
			{
				if (v[j].empty())
				{
					flag = true;
					break;
				}

				if (v[j].back() < min)
					min = v[j].back();
			}

			if (flag)
			{
				cout << -1 << '\n';
				continue;
			}

			int cnt = 0;
			for (int j = 0; j < mod; j++)
				cnt += v[j].end() - lower_bound(v[j].begin(), v[j].end(), min);

			cout << cnt << '\n';
		}
	}

	return 0;
}