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

1. 문제

www.acmicpc.net/problem/20440

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

2. 접근방법

좌표 압축과

Tree set을 이용한 중복제거 및 정렬

이분탐색을 활용하는 문제

 

이 범위에서 실제로 사용되는 부분은

 

2 - 4 까지 같은 값

4 - 6 까지 같은 값

6 - 10 까지 같은 값

10 - 16 까지 같은 값 이다

 

그러니 T에 맞춰 21억개의 좌표를 이용할게 아닌

같은 값을 가지는 좌표들의 범위를 압축시켜 N의 크기 1,000,000만큼의 좌표만 사용하도록 한다.

 

우선 좌표 압축을 위해

T의 모든 값을 값이 들어오면 자동으로 오름차순 정렬과 중복 허용을 하지 않는 Tree Set에 넣어주고

다시 ArrayList로 변환 시킨다.

이러면 좌표압축 끝

 

이제 각 압축된 좌표의 모기 갯수를 카운트 하기위해 List크기의 sum배열 하나 만들어두고

순서대로 T시작 부터 T 끝까지 값들을

binary search를 이용해 index를 뽑아내 sum 배열에 모두 더해준다.

 

이후 sum 배열 중 가장 큰 값을 구해서 출력 해주면 된다.

 

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class G4_20440니가싫어싫어너무싫어싫어오지마 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int sarr [] = new int [N];
		int earr [] = new int [N];
		TreeSet<Integer> temp = new TreeSet<Integer>();
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			sarr[i] = s;
			earr[i] = e;
			temp.add(s);
			temp.add(e);
		}
		ArrayList<Integer> idx = new ArrayList<Integer>(temp);
		int sum[] = new int[idx.size()];
		for (int i = 0; i < N; i++) {
			int x = Collections.binarySearch(idx, sarr[i]);
			int y = Collections.binarySearch(idx, earr[i]);
			for (int j = x; j < y; j++)
				sum[j]++;
		}
		int max = 0;
		int maxidx = -1;
		int maxendidx = -1;
		for (int i = 0; i < idx.size(); i++) {
			if (sum[i] > max) {
				maxidx = i;
				maxendidx = i;
				max = sum[i];
			}
			if (sum[i] == max && i - 1 == maxendidx) {
				maxendidx = i;
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append(max+"\n"+idx.get(maxidx)+" "+idx.get(maxendidx + 1));
		System.out.print(sb);
	}

}

4. 마치며

좌표압축의 개념은 알고 있었지만 실제로 풀어본건 처음인데 생각보다 어려웠다.

익숙해질 때까지 또 풀어봐야겠지