[C++] 백준 20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

문제 링크

20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1

문제 요약

모기들이 방에 들어가고, 나가는 시간이 주어진다. 이때 모기들이 방 안에 가장 많은 시점의 모기 수와, 그 구간을 출력해야 한다. 그러한 구간이 여럿이라면 출발 지점이 가장 빠른 구간을 출력해야 한다.

접근 방법

일단 값이 최대 21억까지 가기 때문에 바로 누적합을 사용하면 MLE에 걸릴 것입니다. 따라서 값 압축이 필요합니다. 처음에는 바로

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

와 std::binary_search() 이용하려고 했는데, 구간도 출력해야되기 때문에 압축된 값을 역으로 저장하는 자료구조도 필요하다고 생각했고, std::map을 사용했습니다. 이것이 TLE를 받았던 이유 중에 하나로 작용했습니다.

이제 압축한 결과를 가지고 누적합을 구해주면 됩니다. 구간의 시작마다 1을 더하고, 끝에서 1을 빼고, 처음부터 누적합을 계산해주면 각 시점에서 모기의 수를 알 수 있습니다.

그렇게 코드를 작성하고 냈는데 TLE를 받았습니다. 처음에는 std::map이 느린편이라서 그럴지도 모른다고 생각을 했습니다. 그래서 std::unordered_map을 사용했는데 그래도 TLE를 받았습니다. 그래서 또 수정해서 위의 std::sort, std::unique, std::erase를 사용하고, 역으로 저장하는 경우는 배열로 처리했는데 이래도 TLE를 받았습니다. 이 코드가 TLE를 받자마자 이럴리가 없다는 생각이 들었고 바로 문제를 알아차렸습니다. 입력값이 100만개에 달하는데, 입출력 속도가 느려서 TLE를 받은 것이었습니다. 이를 수정하니까 바로 AC를 받을 수 있었습니다.

다만, 빠른 입출력을 사용해도 std::map을 사용한 풀이는 TLE가 나왔습니다.

코드1

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> v;
	vector<pair<int, int>> input;

	for (int i = 0; i < n; i++)
	{
		int e, x;
		cin >> e >> x;
		input.push_back({ e, x });
		v.push_back(e);
		v.push_back(x);
	}

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	vector<int> rev(v.size()), sum(v.size());
	for (auto& i : input)
	{
		int val1 = lower_bound(v.begin(), v.end(), i.first) - v.begin();
		int val2 = lower_bound(v.begin(), v.end(), i.second) - v.begin();
		rev[val1] = i.first;
		rev[val2] = i.second;
		sum[val1]++;
		sum[val2]--;
	}

	for (int i = 1; i < sum.size(); i++)
		sum[i] += sum[i - 1];

	int res = 0;
	for (auto& i : sum)
		res = max(res, i);

	cout << res << '\n';

	int em, xm;
	bool flag = false;
	for (int i = 0; i < sum.size(); i++)
	{
		if (!flag && sum[i] == res)
		{
			flag = true;
			em = rev[i];
		}
		if (flag && sum[i] != res)
		{
			xm = rev[i];
			break;
		}
	}

	cout << em << ' ' << xm;
	return 0;
}

코드2(해시맵)

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> v;
	vector<pair<int, int>> input;
	unordered_map<int, int> m, rev;

	for (int i = 0; i < n; i++)
	{
		int e, x;
		cin >> e >> x;
		input.push_back({ e, x });
		v.push_back(e);
		v.push_back(x);
	}

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

	int idx = 0;
	for (auto& i : v)
	{
		if (m.find(i) == m.end())
		{
			m.insert({ i, idx });
			rev.insert({ idx++, i });
		}
	}

	vector<int> sum(idx);
	for (auto& i : input)
	{
		sum[m[i.first]]++;
		sum[m[i.second]]--;
	}

	for (int i = 1; i < sum.size(); i++)
		sum[i] += sum[i - 1];

	int res = 0;
	for (auto& i : sum)
		res = max(res, i);

	cout << res << '\n';

	int em, xm;
	bool flag = false;
	for (int i = 0; i < sum.size(); i++)
	{
		if (!flag && sum[i] == res)
		{
			flag = true;
			em = rev[i];
		}
		if (flag && sum[i] != res)
		{
			xm = rev[i];
			break;
		}
	}

	cout << em << ' ' << xm;
	return 0;
}