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

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

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

 

 

 

 

 

 

문제

• 모기들의 방 입장, 퇴장 시각이 주어졌을 때 모기들이 가장 많이 있는 시간대와 해당 시간대에 모기가 몇 마리가 있는지 구하기

 

제한 사항

• 모기의 마릿수 N(1 ≤ N ≤ 1,000,000)
• 모기의 입장 시각 TE과 퇴장 시각 TX (0 ≤ TE < TX ≤ 2,100,000,000)
• 모기는 [TE, Tx)동안 존재

 

 

 

 

 

풀이

처음 생각난 풀이는 좌표계를 배열로 표현해서, 해당 좌표에 모기가 있다는 것을 기록하는 것이었다. 하지만 문제가 있었다. 모기가 있는 연속된 모든 구간에 모두 +1을 해주면, N개의 구간마다 입장 시각부터 퇴장 시각 전까지 +1을 해줘야 하기 때문에 많은 시간이 걸린다.

 

 

 

 

 입장 시각부터 퇴장시각까지 모두 +1을 해주는 것을 막기 위해서, 시작 시각이면 해당 좌표의 값을 +1을 해주고, 끝점이면 -1을 해주는 방식으로 좌표별 모기 수를 누적해서 더해나간다.

 

 

 

 하지만 이 문제에서는 좌표계를 배열을 사용해서 나타낸다면 OutOfMemoryErrorr 날 것이다. 왜냐하면 퇴장 시각이 최대 21억으로 매우 크기 때문이다. 좌표계의 범위가 작은 경우에는 상관이 없겠지만, 범위가 큰 경우에는 좌표계를 배열로 표현한다면 메모리 낭비에다가 탐색을 하는데 많은 시간이 걸릴 것이다.

백준에서 이 문제의 카테고리에 '좌표 압축'이 있는 이유가 있다.

 

 

 문제에서 주어진 좌표의 범위를 모두 쓸 필요가 없다. 모기의 마릿수는 최대 100만으로, 모든 입장 시간과 퇴장 시간을 표현한다면 최대 200만개의 좌표가 쓰일 것이다. 21억보다는 매우 작은 수이다.

 

 

 

[방법1] HashMap 사용

 

• 시각 별 모기수 저장하기

 모기의 입장 시각과 퇴장 시각을 입력받을 때, 시각을 key로 하는 map에 모기수의 개수를 갱신하면서 저장한다.

 

• key(시각) 오름차순으로 정렬하기

모기가 있는 시각별 모기의 수를 누적해서 합해야 하므로, 시각(key) 오름차순으로 map을 정렬한다.

 

• key(시각)에 해당하는  value(모기수) 누적합 구하기, 최댓값 갱신하기

 정렬된 key값인 모기가 있는 시각을 모두 순회하며 누적합을 구해나간다. 그리고 누적합이 최댓값이면 max를 갱신해주고, 입장 시각도 갱신해준다. 그리고 최대 구간에서 값이 바뀌는 지점이면 퇴장 시각을 갱신해준다. 

 

 

 

 

코드

package algorithm;

import java.io.*;
import java.util.*;

public class BOJ_니가싫어싫어 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); //모기 마릿수

		HashMap<Integer, Integer> map = new HashMap<>();
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");

			int TE = Integer.parseInt(st.nextToken());
			int TX = Integer.parseInt(st.nextToken());
			
			map.put(TE, map.getOrDefault(TE, 0) + 1);
			map.put(TX, map.getOrDefault(TX, 0) - 1);
		}
		
		//맵 키 오름차순 정렬
		List<Integer> keyList = new ArrayList<>(map.keySet());
		keyList.sort((o1, o2) -> o1 - o2);
		
		int sum = 0;
		int max = 0;
		int ans_start = 0, ans_end = 0;
		
		//맵 순회하며 찾기
		boolean opened = false; //최대 구간이 열렸는지
		
		for(int key : keyList) {
			sum += map.get(key); //+1 or -1값을 누적시킴
			
			if(sum > max) { //최댓값이 나오면 갱신
				max = sum;
				ans_start = key;
				opened = true;
			} else if(sum < max && opened) { //최대 구간에서 값이 바뀌는 지점이면
				ans_end = key;
				opened = false; //구간 닫음
			}
		}
		
		System.out.println(max);
		System.out.println(ans_start + " " + ans_end);
	}

}

 

 

1500ms대로 800~900ms대의 풀이보다는 꽤 오래 걸렸다.

 

비슷한 로직인데, map에 저장하는 과정에서 map에 있는 key의 value를 찾고, 갱신해서 다시 저장하는 작업을 하니 시간이 꽤 드는 것 같다.

 

 

 

 

 

[방법2] 2 * N 크기의 배열 사용

 

• 시각과 입퇴장 값 저장하기

 N번의 입장 시각과 퇴장 시각을 저장하기 위해 2 * N 크기의 배열을 썼다. 2차원 배열에 저장했는데, 0열에는 시각을 저장하고, 1열에는 입장이면 1, 퇴장이면 -1을 저장하도록 했다. 

 

 

• 시각 오름차순으로 정렬하기

 모기가 있는 시각별 모기의 수를 누적해서 합해야 하므로 시각 오름차순으로 정렬한다. 그리고 시각이 같은 경우에는 입장 시각인 경우가 퇴장 시각인 경우보다 앞서도록 한다. 입장 시각의 값이 퇴장 시각의 값보다 먼저 계산되어야 하기 때문이다.

 

• 모기의 누적합 구하기, 최댓값 갱신하기

 map일때는 시각 하나에 있는 총 모기수가 저장되었지만, 배열에는 같은 시각이 여러 번 저장되었기 때문에 같은 시각이 나올 때까지 값을 더해야 한다. (이 부분만 주의하면 뒤의 로직은 같다.)

 

 그리고 누적합이 최댓값이면 max를 갱신해주고, 입장 시각도 갱신해준다. 그리고 최대 구간에서 값이 바뀌는 지점이면 퇴장 시각을 갱신해준다. 

 

 

 

 

 

코드

package algorithm;

import java.io.*;
import java.util.*;

public class BOJ_니가싫어싫어2 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
		int N = Integer.parseInt(br.readLine()); //모기 마릿수
		
		int[][] arr = new int[2 * N][2];
		
		for(int i = 0; i < N; i ++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");

			int TE = Integer.parseInt(st.nextToken());
			int TX = Integer.parseInt(st.nextToken());

			arr[2 * i] = new int[] {TE, 1};
			arr[2 * i + 1] = new int[] {TX, -1};
		}
		
		Arrays.sort(arr, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
		
		int sum = 0;
		int max = 0;
		int ans_start = 0, ans_end = 0;
		
		boolean opened = false; //최대 구간이 열렸는지
		
		int i = 0;
		while(i < 2 * N) {
			int cur_time = arr[i][0];
			
			while(i < 2 * N && arr[i][0] == cur_time) {
				sum += arr[i][1];
				i++;
			}
			
			if(sum > max) { //최댓값이 나오면 갱신
				max = sum;
				ans_start = cur_time;
				opened = true;
			} else if(sum < max && opened) { //최대 구간에서 값이 바뀌는 지점이면
				ans_end = cur_time;
				opened = false; //구간 닫음
			}
		}
		
		System.out.println(max);
		System.out.println(ans_start + " " + ans_end);
	}

}

 

 

 

 

 

결과

 

[방법1] HashMap 사용 : 1500ms대

[방법2] 2 * N 크기의 배열 사용 : 900ms대

 

 

 

 

 

배운점

• 구간의 모든 점들을 저장할 필요 없이 시작점은 +1, 끝점은 -1을 저장하자
• 좌표계의 범위가 클 때는 좌표 압축을 하자