[JAVA] 백준 20440 니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마

오늘의 문제 : https://www.acmicpc.net/problem/20440

 

아니 모기송하면 이광수 님의 모기송 아닌가요?

나참.

 

처음에는 PQ를 사용하여 도전을 해봤는데 계속 실패해서 다른 분의 코드를 흡수헀습니다. 

 

HashMap을 사용하여 특정 시간에 모기가 얼마나 들어고 나갔는지를 저장하는 방법입니다. 

 

HashMap을 사용한 이유는 모기가 들어오고 나간 시간 사이는 탐색을 할 필요가 없어서 라고 생각합니다.

 

예를 들어 1,20에 모기가 들어왔다면, 그 사이 수 2,3,4,.. 19는 다 같은 모기 수를 갖고 있음으로 탐색할 필요가 없습니다. 

 

문제에서 시간의 최대 값를 21억으로 말한 것도 힌트가 될 수 있겠습니다. 

 

구현은 간단합니다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Num2044니가_싫어싫어 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int maxSize = 0;
        int s = 0;
        int e = 0;
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int nowS = Integer.parseInt(st.nextToken());
            int nowE = Integer.parseInt(st.nextToken());
            hashMap.put(nowS,hashMap.getOrDefault(nowS,0)+1);
            hashMap.put(nowE,hashMap.getOrDefault(nowE,0)-1);
        };
        List<Integer> keys = new ArrayList<>(hashMap.keySet());
        keys.sort(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o1-o2;
            }
        });
        int nowMos = 0;
        boolean isChange = false;
        for(int i : keys){
            nowMos += hashMap.get(i);
            if(nowMos > maxSize){
                maxSize = nowMos;
                s = i;
                isChange = true;
            }else if(nowMos<maxSize && isChange){
                isChange = false;
                e = i;
            }
        }
        System.out.println(maxSize);
        System.out.println(s + " "+e);
    }
}

 

후기 여기서 부터는 틀린 풀이가 나옵니다.

 

왜 PQ를 사용하여 푸는데 실패했을까요. 여기서라도 하소연을 해야겠어요.

 

PQ에는 끝나는 시간만 넣어줬습니다. 그리고 그다음의 모기가 들어오는 시간과 PQ의 Peek 한 값을 비교하여 상황을 나눴습니다.

 

1. 다음 모기가 들어오는 시간이 큰 경우

  PQ에서 다음 모기가 들어오는 시간보다 큰 값이 Peek 될때 까지 빼낸다.

2. 다음 모기가 들어오는 시간이 같은 경우

  PQ를 한번 poll 하고, 다음 모기가 끝나는 시간을 넣어준다. 

3. 다음 모기가 들어오는 시간이 더 작은 경우

  PQ를 poll하지 않고 다음 모기가 끝나는 시간을 넣어준다. 

 

그리고 PQ의 사이즈가 커질 때마다 그 값을 저장하고, 그때 들어온 시작값을 저장해 줬습니다.

PQ의 사이즈가 작아진다면 그때 그 값을 저장... 했어야 했구나. 잠시만요. 

 

흠 거의 다 맞았는데..