Java
[백준 20440] 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (JAVA)
iheeeee6-6
2023. 2. 21. 12:00
728x90
https://www.acmicpc.net/problem/20440
20440번: 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1
첫째 줄에 지동이의 방에 출입한 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)가 주어진다. 다음 N개의 줄에 모기의 입장 시각 TE과 퇴장 시각 TX이 주어진다. (0 ≤ TE < TX ≤ 2,100,000,000) 모기는 [TE, Tx)동
www.acmicpc.net
Map을 사용하여 문제를 해결하였다.
모기가 들어올때 +1, 나갈때 -1을 하여
가장 큰 값을 가진 시간이 모기가 가장 많은 시간인 것이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Map<Integer,Integer> map = new HashMap<>();
Map<Integer,Integer> map2 = new HashMap<>();
StringTokenizer st;
for(int i=0;i<n;i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
map.put(start, map.get(start)!=null? map.get(start)+1:1);
map.put(end, map.get(end)!=null? map.get(end)-1:-1);
}
ArrayList<Integer> arrlist =new ArrayList<>(map.keySet());
Collections.sort(arrlist);
int count=0;
int maxCount=0;
int maxstart=0;
int maxend=0;
int maxstartidx=0;
for(int i=0;i<arrlist.size();i++) {
int temp =count+map.get(arrlist.get(i));
count=temp;
map2.put(arrlist.get(i), temp);
if(maxCount<temp) {
maxCount=temp;
maxstart=arrlist.get(i);
maxstartidx=i;
}
}
while(true) {
if(map2.get(arrlist.get(++maxstartidx))!=maxCount)
{
maxend= arrlist.get(maxstartidx);
break;
}
}
System.out.println(maxCount);
System.out.println(maxstart+" "+maxend);
}
}