[골드3] 20440. 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (Java)

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

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

 🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵🎵

 

---

※  문제를 요약하면 아래와 같습니다.

▶ 지동이의 방에 모기의 수와 각 모기별 활동 시간이 주어졌을 때, 모기가 제일 많이 존재하는 시간 출력

▶ Input : 첫째 줄에 모기의 마리수 N (1 <= 1,000,000 ), 다음 N 개의 줄에 모기의 입장 시각과 퇴장 시각 주어짐

                 시각 T  -->  0 <= T <= 2,100,000,000

▶ Output : 첫째 줄에 모기가 제일 많은 시간대의 모기 수, 둘째 줄에 가장 많이 있는 시간대를 출력

---

◈ Input - 1

3
2 16
4 6
6 10

◈ Output - 1

2
4 10

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 2,100,000,000 까지 시간 + N은 1,000,000 까지 주어지기 때문에 누적합 하면 당연히 시간복잡도가 1초 이상 발생

▶ HashMap의 Key를 시각, value를 모기 수로 저장

▶ 한 번이라도 주어졌던 시각을 중복 없이 ArrayList로 저장 ( 코드 내 listTime)

▶ 저장 이후, 아래와 같은 순서로 모기가 많은 시간을 탐색

    1. listTime을 정렬 => 숫자가 적은 시간대부터 탐색 ( 모기가 많은 수의 시간이 여러개일 경우, 작은 시간대 출력 )

    2. Input-1의 2, 4, 6 처럼 시작 시각을 Key로 갖는 value는 +1, 

       Input-1의 16,6,10 처럼 종료 시각을 Key로 갖는 value는 -1을 HashMap에 적용

       위의 과정에서 최대 모기수와 해당 하는 인덱스를 저장 ( == 모기의 최대 수를 가진 시간대가 시작하는 시각 )

    3. 2번의 과정에서 저장된 인덱스 부터 리스트에 저장된 다음 인덱스의 시간 대가 Max값과 다를 때 까지 탐색

         == 모기의 최대 수를 가진 시간대가 끝나는 시각

▶ 최대 모기 수 및 해당 시간대 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		// 배열 값을 입력받자
		int N = Integer.parseInt(bReader.readLine());

		HashMap<Integer, Integer> mapMos = new HashMap<>();
		ArrayList<Integer> listTime = new ArrayList<>();
		
		
		int nMax = 0;
		int nMinIndex = Integer.MAX_VALUE;
		
		// Rule 1 : First Time + 1, End Time - 1
		//        : listTime save the time from inputs
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(bReader.readLine());
			int nStart = Integer.parseInt(st.nextToken());
			int nEnd = Integer.parseInt(st.nextToken());

			if (!mapMos.containsKey(nStart)) {
				mapMos.put(nStart, 1);
				listTime.add(nStart);
			}
			else
				mapMos.put(nStart, mapMos.get(nStart)+1);
			
			if(!mapMos.containsKey(nEnd)) {
				mapMos.put(nEnd, -1);
				listTime.add(nEnd);
			}
			else
				mapMos.put(nEnd, mapMos.get(nEnd) - 1);
		}
		
		int nVal = 0;
		int nIndex = -1;
		int nLastIndex = -1;
		
		// Sort the time to start from minimum time.
		Collections.sort(listTime);
		
		// Rule 2 : Update the maps by rule 1, 2, save the maximum value and the index (time)
		for(int i = 0; i < listTime.size(); i++) {
			nVal += mapMos.get(listTime.get(i));
			if(nMax < nVal) {
				nMax = nVal;
				nIndex = i;
			}
			mapMos.put(listTime.get(i), nVal);
		}
		
		// Rule 3: get the end time which has max mos;
		nVal = nMax;
		nLastIndex = nIndex;
		while(nMax == nVal) {
			if(nLastIndex >= listTime.size()) {
				nLastIndex--;
				break;
			}
			nVal = mapMos.get(listTime.get(nLastIndex));
			
			if(nVal != nMax)
				break;
			
			nLastIndex++;
		}
		
		
		bWriter.write(nMax + "\n");
		bWriter.write(listTime.get(nIndex) + " " + listTime.get(nLastIndex));

		bWriter.close();
	}

}

---

Good Luck! (피드백 감사합니다!)