[G3] 백준 20440번 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 C++ 정렬, 값/좌표 압축, 누적합, 차분 배열 트릭

리뷰

 

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

문제 제목이 왜이렇게 긴걸까

 

 

전역 변수

• N : 배열의 최대 길이를 정의할 상수 변수
• mos : 모기의 등장 시간을 저장할 배열
• n : 모기의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, 정수형 변수 times를 초기화한다.
2. n마리의 모기의 진행 시간을 입력 받아 mos, times를 초기화 해준다.
3. sort함수를 통해 times를 오름차순으로 정렬하고, erase, unique함수를 통해 중복을 제거해준다.
4. 변수 m에 times의 크기를 저장하고, 정수형 벡터 diff를 m+1크기로, 초기값은 0으로 초기화한다.
5. n마리의 모기 정보를 순회하며 변수 si, ei에 모기의 입장 시간과 퇴장 시간의 인덱스를 times로부터 구해준다.
6. diff[si]를 증가시키고, diff[ei]를 감소시켜 차분 배열을 초기화한다.
7. 변수 mx, cur을 0으로 초기화 하고, diff를 기반으로 모기가 가장 많을 때의 마릿수를 mx에 저장한다.
8. 변수 si, ei, cur을 0으로 초기화, flag를 false로 초기화하고, 다시 cur에 차분값을 더한다.
9. cur이 mx에 도달했을때부터 구간을 측정하여 cur이 mx가 아니게 되었을때 종료한다.
10. mx를 출력하고 개행문자를 삽입해 줄바꿈을 수행하고, si, ei를 공백을 기준으로 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1.  (0 ≤ TE < TX ≤ 2,100,000,000)이므로 값/좌표 압축을 통해 인덱싱이 필요하다.
2. 해당 인덱스를 기준으로 누적합을 수행한다.

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;

const int N = 1e6;
pii mos[N];
int n;

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

	cin >> n;
	vector<int> times;
	for (int i = 0; i < n; ++i) {
		int st, et; cin >> st >> et;
		mos[i] = { st, et };
		times.push_back(st);
		times.push_back(et);
	}

	sort(times.begin(), times.end());
	times.erase(unique(times.begin(), times.end()), times.end());
	int m = times.size();
	
	vector<int> diff(m + 1, 0);
	for (int i = 0; i < n; ++i) {
		int st = mos[i].first;
		int et = mos[i].second;

		int si = lower_bound(times.begin(), times.end(), st) - times.begin();
		int ei = lower_bound(times.begin(), times.end(), et) - times.begin();

		++diff[si];
		--diff[ei];
	}

	int mx = 0;
	int cur = 0;
	for (int i = 0; i < m; ++i) {
		cur += diff[i];
		if (cur > mx) mx = cur;
	}

	long long si = 0, ei = 0;
	cur = 0;
	bool flag = false;
	for (int i = 0; i < m; ++i) {
		cur += diff[i];

		if (cur == mx) {
			if (!flag) {
				flag = true;
				si = times[i];
			}
			ei = times[i + 1];
		}
		else if (flag) break;
	}

	cout << mx << "\n" << si << " " << ei;
}