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

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

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

 

전체적인 풀이 방법은, 모기가 들어오는 시각에 +1, 나가는 시각에 -1을 하여, 누적합을 통해 가장 모기의 수와 해당 시간대를 구하는 문제지만, 시각의 범위가 너무 커서, 시각을 인덱스로 하는 배열에 +1, -1을 수행할 수 없다. 이를 위해 배열이 아닌, unordered_map의 [시각] 위치에 +1,-1을 수행해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

int n;
unordered_map<int, int> range;
vector<int> time_list;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int e, x;
		cin >> e >> x;

		if (range.count(e) == 0) {
			range.insert(make_pair(e, 1));
		}
		else {
			range[e] += 1;
		}

		if (range.count(x) == 0) {
			range.insert(make_pair(x, -1));
		}
		else {
			range[x] -= 1;
		}

		time_list.push_back(e);
		time_list.push_back(x);
	}

	//중복되는 시간 제거
	sort(time_list.begin(), time_list.end());
	time_list.erase(unique(time_list.begin(), time_list.end()), time_list.end());

	int max_sum = -1;
	pair<int, int> max_range = make_pair(-1, -1);

	int check_sum = 0;
	for (int i = 0; i < time_list.size(); i++) {

		check_sum += range[time_list[i]];

		//더 큰 모기수를 발견 했을때
		if (max_sum < check_sum) {
			max_sum = check_sum;
			max_range.first = time_list[i];
			max_range.second = -1; //끝나는 범위 초기화
		}

		//이전에 더 큰 모기수를 발견한 경우여서 범위가 끝나는 경우일때
		else if (max_sum > check_sum && max_range.second == -1) {
			max_range.second = time_list[i];
		}
	}

	cout << max_sum << "\n";
	cout << max_range.first << " " << max_range.second << "\n";

	return 0;
}