BOJ - 17364

BOJ - 17364

(문제 : https://www.acmicpc.net/problem/17364)

UCPC 2021을 준비하면서, 2019 UCPC C번 문제를 풀었음.

먼저 생각한 방법

1. 먼저 대회 시작일(s)을 기준으로 오름차순 정렬. s가 같을 경우 e를 기준으로 오름차순 정렬.
2. N만큼 정수형 배열(person[])을 선언하여 형섭이가 1등하는 것을 막을 인원이 몇 명인지 확인.
3. 1) 만약 person[i]가 0 이상일 경우 end[i]번째보다 작은 start[j]에서 person[j]를 감소시킨다(person[j]--).
   2) 만약 person[i]가 0 이라면 형섭이가 참여하여 1등을 하고, e보다 큰 s[j]번을 찾아 다시 3번을 시행한다.
4. 3 - 1), 3 - 2) 과정을 반복한다.
   -> 이렇게 하면 효율적으로 형섭이 1등을 막는 경우가 아님.(종료일과 시작일이 가까울수록 효율적)

문제 해결 방법

1. 먼저 대회 종료(e)를 종료일을 기준으로 오름차순 정렬. e가 같을 경우 s를 기준으로 오름차순 정렬.
2. treeMap을 선언하여 종료일을 담는 변수를 만듬. (단, K가 1이 아닐 경우.)
   (c++에서는 multiSet을 이용하지만, 자바에선 없기때문에 treeMap으로 중복된 값이 있다면 value를 증가.)
3. 형섭이의 시간을 처음에 0으로 초기화 한 후, 반복문을 통해 0 ~ N - 1까지 start와 end를 비교.
4. time >= start일 경우 : 다음 배열 확인(continue)
5. time < start일 경우
   1) map에서 lowerkey를 못찾았을 경우 형섭이 참여할 수 있으므로, count++ 후 time을 end값으로 변경.
   2) map에서 lowerkey를 찾았을 경우 map에서 lowerkey에 해당하는 값을 지우고(key에 대한 value가 1 이상이면 -1, 1이면 remove), map에 end값을 추가(key에 대한 value가 있다면 +1, 없다면 put(end, 1))
6. 반복문이 끝날때까지 4) ~ 5)를 반복.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	public static class Node implements Comparable<Node>{
		int start;
		int end;
		
		Node(int start, int end){
			this.start = start;
			this.end = end;
		}
		
		@Override
		public int compareTo(Node o) {
			if(o.end != this.end) {
				return this.end - o.end;
			}
			else {
				return this.start - o.start;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		
		Node[] list = new Node[N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			
			list[i] = new Node(s, e);
		}
		
		Arrays.sort(list);
		TreeMap<Integer, Integer> map = new TreeMap<>();
		
		if(K != 1) map.put(0, K - 1);
		
		int count = 0, time = 0;
		
		for(int i = 0; i < N; i++) {
			Node curNode = list[i];
			int curStart = curNode.start;
			int curEnd = curNode.end;
			
			if(time >= curStart) {
				continue;
			}
			
			if(map.lowerKey(curStart) == null) {
				count++;
				time = curEnd;
			}
			else {
				int tmp = map.lowerKey(curStart);
				
				if(map.get(tmp) == 1) {
					map.remove(tmp);
				}
				else {
					map.put(tmp, map.get(tmp) - 1);
				}
				
				if(map.containsKey(curEnd)) {
					map.put(curEnd, map.get(curEnd) + 1);
				}
				else map.put(curEnd, 1);
			}
		}
		
		System.out.println(count);
	}

}

후기

그리디 문제임을 알았지만, 어떤 방식으로 해결해야 최적의 해인지 제대로 몰라서 애먹었음. UCPC 2019 예선 풀이를 참고하여 아이디어를 얻음.
UCPC 2019 예선 풀이.pdf