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

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

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

 

무지성 트리맵 자료구조를 사용하면 시간초과에 거의 근접한 성능으로 겨우 통과를 받을 수 있는 문제다.

트리맵이라는 자료구조 자체가 무거운 자료구조일 뿐만 아니라 key를 기준으로 정렬되어있지만 value를 기준으로 원하는 값을 찾고자 할때는 iterator를 이용한 선형탐색밖에 답이 없으므로 트리맵을 쓰는 것은 좋지 않다.

 

vector자료구조와 sort, unique, lower_bound 를 이용한 좌표압축 기법을 쓰는 것이 정해로 보인다. 다만 나는 이 문제를 풀면서 불필요한(?, 불필요한건 아니지만 임시로 사용되는 이 옳은 표현인 것 같다.) 배열에 메모리를 사용하고 싶지 않아서 고민 끝에 그냥 벡터 하나에 좌표값과 prefix_sum 값을 같이 넣어서 해결했다.

 

0. dp기법중 prefix_sum(누적합) 기법을 사용했다.

1. 모기가 들어오는 지점에 prefix_sum 값을 +1 해준다.

2. 모기가 나가는 지점에 prefix_sum 값을 -1 해준다.

3. 모든 지점을 좌표값 기준 오름차순으로 순회하면서 차례대로 이전 인덱스의 prefix_sum 값을 현재 지점의 prefix_sum 값에 더한다.

4. 벡터의 사이즈만큼 모두 순회했다면 벡터의 각 지점에는 현재 모기가 몇 마리 있는지 갱신되어있다.

 

+5. 나는 좌표압축을 하지 않았기 때문에 좌표가 unique하지 않다. 따라서 while문 안에서 while문을 한 번 더 돌면서 좌표가 같은 값을 모두 더해줬다.

 

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

using namespace std;

int n;
vector<pair<int,int>> prefix_sum;

void solution() {
	int in, out;
	int cur_pos, prev, max_val;
	int idx, start, end = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> in >> out;
		prefix_sum.emplace_back(in, 1);
		prefix_sum.emplace_back(out, -1);
	}

	sort(prefix_sum.begin(), prefix_sum.end());
	
	idx = 0, prev = 0, max_val = 0;
	while (idx < prefix_sum.size()) {
		cur_pos = prefix_sum[idx].first;
		//좌표 압축을 하지 않아 좌표 값이 unique하지 않음
		//while문을 한 번 더 돌면서 좌표 값이 같은 동안 prefix_sum 값을 더해줌
		while (idx < prefix_sum.size()
			&& prefix_sum[idx].first == cur_pos) {
			prev += prefix_sum[idx].second;
			++idx;
		}

		if (prev > max_val) {
			max_val = prev;
			start = cur_pos;
			end = 0;
		}
		else if (prev < max_val) {
			if (!end) end = prefix_sum[idx - 1].first;
		}
	}
	cout << max_val << '\n';
	cout << start << ' ' << end << '\n';
}

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

	return 0;
}

메모리: 26728 kb

시간: 300 ms