[누적합/좌표압축] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1(20440)(C++)

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

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

 

1. 문제 개요

 

모기를 싫어하는 지동이는 어느 날 문득 자신의 방에 모기가 가장 많이 있는 시간대가 언제인지 궁금해졌다. 다행히 지동이 방은 최첨단 시스템이 갖춰져 있어 어떤 모기가 방에 언제 입장했고 언제 퇴장했는지를 기록할 수 있다.

지동이를 도와 모기들의 방 입장, 퇴장 시각이 주어졌을 때 모기들이 가장 많이 있는 시간대와 해당 시간대에 모기가 몇 마리가 있는지 구하는 프로그램을 만들어보자. 

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

누적합을 이용해서 값이 가장 큰 구간을 구하는 문제.

모기의 입장 시간과 퇴장 시간의 값이 최대 2,100,000,000 이기 때문에 단순히 다른 누적합처럼 배열이나 벡터를 사용했다간 메모리가 초과될 것이다. 

따라서 좌표압축을 한 다음 누적합을 구해준다.

 

좌표압축은 하나의 벡터에 모기가 들어온 시간과 나간 시간을 넣어준 다음에 벡터를 소트하고 유니크함수를 통해 같은 값을 지워주면 된다.

// 좌표압축
sort(v.begin(), v.end());
v.erase(unique(v.begin(),v.end()),v.end());

그 다음에 lower_bound를 통해서 벡터 안의 값의 인덱스를 통해 좌표를 사용하면 된다.

int value; // 원래 값
lower_bound(v.begin(),v.end(),value)-v.begin()]; // 좌표 압축을 한 후의 값

 

두 가지 이유로 틀렸는데 첫번째는 배열의 범위를 모기의 수인 1000001로 해서였다. 들어온 시간, 나간 시간 두가지 시간의 범위가 있기 때문에 배열의 범위를 모기의 수의 두 배인 2000002로 해주었더니 이 부분은 해결되었다.

 

그 다음으로는 하나의 for문 안에서 max, Te(시작시간), Tx(종료시간) 이 세가지 값을 한 번에 구하려했기 때문이었다. 정확히 어떤 점이 틀리게끔 한지는 모르겠지만, 첫번째 for문에서 max 값을 먼저 구한 다음에 두 번째 for문에서 Te, Tx를 구하는 방식이 나은 것 같다. 이렇게 두 가지를 고쳐주었더니 통과되었다.

 

 

4. 전체 코드

 

//
//  20440.cpp
//  baekjoon
//
//  Created by 배주현 on 2022/07/01.
//

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

using namespace std;

int N;
int sum[2000002], arr[2000002];

int main(void) {
    scanf("%d",&N);
    vector<pair<int, int>> pv; // 초기에 모기가 출퇴한 시각을 저장
    vector<int> v; // 압축한 좌표의 값을 저장
    
    for (int i=0;i<N;i++) {
        int tmp1, tmp2;
        scanf("%d%d",&tmp1,&tmp2);
        pv.push_back({tmp1,tmp2});
        v.push_back(tmp1);
        v.push_back(tmp2);
    }
    
    // 좌표압축
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    
    for(int i=0;i<pv.size();i++) {
        sum[lower_bound(v.begin(),v.end(),pv[i].first)-v.begin()] += 1;
        sum[lower_bound(v.begin(),v.end(),pv[i].second)-v.begin()] -= 1;
    }
    
    for (int i=1;i<v.size();i++)
        sum[i]+=sum[i-1];
    
    int maxN=0;
    for(int i=0;i<v.size();i++) {
        maxN = max(maxN,sum[i]);
    }
    
    int Te = 0,Tx = 0;
    for (int i=0;i<v.size();i++) {
        if(Tx==0 && sum[i]==maxN) {
            Te = v[i]; // 압축했던 좌표를 다시 품
            Tx = -1;
        }
        if(Tx==-1 && sum[i]!=maxN) {
            Tx = v[i];
            break;
        }
    }
    
    printf("%d\n%d %d\n",maxN,Te,Tx);
}