[백준 C++] 10816 : 숫자 카드 2

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

주어지는 수의 범위가 굉장히 크기 때문에, 시간초과에 유의해서 풀어야 한다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N, M;
	vector<int> list;
	vector<int> input;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;

		list.push_back(temp);
	}

	sort(list.begin(), list.end());

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		int temp;
		cin >> temp;

		input.push_back(temp);
	}

	for (int i = 0; i < input.size() - 1; i++)
		cout << upper_bound(list.begin(), list.end(), input.at(i)) - lower_bound(list.begin(), list.end(), input.at(i)) << " ";
	cout << upper_bound(list.begin(), list.end(), input.at(input.size() - 1)) - lower_bound(list.begin(), list.end(), input.at(input.size() - 1)) << endl;

	return 0;
}

이 문제의 경우 upper_bound와 lower_bound를 사용하라고 만든 문제같이 느껴졌다.

물론 다른 방법은 있겠지만, 시간초과를 해결하기 위해선 이 방법이 최선일 것이라고 생각하였다.

upper_bound는 범위 중에 주어진 값보다 큰 값의 첫번째 원소 인덱스를 리턴하고, lower_bound는 범위 중에 주어진 값보다 크거나 같은 첫번째 원소 인덱스를 리턴한다.

이 두 함수는 이분 탐색으로 확인하기 때문에 시간복잡도 O(log(End - Start))을 가지게 된다.

두 함수를 사용해 차를 구하면, 원하는 원소가 리스트에 몇개 있는지 확인할 수 있다.

 

+ 아까워서 올리는 실패 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> list;
vector<int> ans;

int findValue(int value)
{
	for (int i = 0; i < list.size(); i++)
	{
		if (list.at(i).first > value)
			return 0;
		else
		{
			if (list.at(i).first == value)
				return list.at(i).second;
		}
	}
}

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

	int N, M;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		
		auto check = find_if(list.begin(), list.end(), [&temp](const pair<int, int>& elem) { return elem.first == temp; });
		if (check != list.end())
		{
			int value = check->second;
			list.erase(check);
			list.push_back(make_pair(temp, value + 1));
		}
		else
			list.push_back(make_pair(temp, 1));
	}

	sort(list.begin(), list.end());

	cin >> M;

	for (int i = 0; i < M; i++)
	{
		int input;
		cin >> input;

		ans.push_back(findValue(input));
	}

	for (int i = 0; i < ans.size() - 1; i++)
		cout << ans.at(i) << " ";
	cout << ans.at(ans.size() - 1);

	return 0;
}

이미 for문 안에 find_if가 들어가서 시간복잡도가 증가한 코드이다.

pair을 사용하여 값을 갱신하려고 한 점이 문제라고 생각한다.

하지만 이 코드를 작성하면서 pair에 first 값 또는 second 값을 비교하는 방법을 알았기 때문에, 이 후에 이 점을 활용할 수 있을 것 같다.