https://www.acmicpc.net/problem/17364
시간 1.5초, 메모리 1024MB
input :
- N K(1 ≤ N ≤ 100,000)(1 ≤ K ≤ 100,000)
- Si Ei(1 <= Si Ei <= 1000000000)
output :
- 형섭이가 우승할 수 있는 최대 대회 수가 가장 적어지도록 K-1명이 대회에 적절히 참가할 때, 형섭이가 우승할 수 있는 대회 수를 출력한다.
조건 :
-
즉, 형섭이가 프로그래밍 대회에서 우승하려면 형섭이보다 잘하는 사람이 대회에 참가하지 않아야 하며 그런 대회에서는 형섭이가 항상 우승한다.
-
전세계에서는 총 N개의 프로그래밍 대회가 개최되며 각 대회는 Si일차부터 Ei일차까지 열린다. 대회가 열리는 장소가 다르므로 어느 누구라도 기간이 겹치는 대회는 동시에 참가할 수 없다.
형섭이가 우승을 가장 적게 하는 경우의 수를 출력해야 한다.
형섭이가 대회를 가장 많이 참여하려면 어떤 순서로 참여해야 할까??
정렬
시작하는 순서 혹은 끝나는 순서로 정렬을 할 수 있다.
이 때 강의실 배정인지 그와 같은 문제에서 끝나는 순서로 정렬을 할 경우 가장 많은 배정이 가능 했던거 같다.
그와 비슷하게 끝나는 순서대로 정렬을 하고 다음 시작하는 대회의 시작시간과 끝나는 시간을 비교한다.
경쟁자
경쟁자들이 하는 방식이 중요하다.
경쟁자의 기준으로서는 형섭이를 방해하는 것이 최우선이다.
따져야 하는 부분은 2가지 정도가 있다.
- 형섭이가 끝나는 시간이 다음 대회 시작시간과 겹치는 경우
-> 이 때는 그냥 무시해도 된다. - 형섭이가 참여할 수 있는 경우
-> 이 때는 참가하면서 형섭이가 참여를 못하게 한다.
예외
참가하는 경우 따져야 하는 것이 존재한다.
대회가 시작하는 시간 기준으로 여러 참여자들이 참가할 수 있을 것이다.
근데 이 중에서 가장 효율적으로 하려면 어떻게 해야 할까.
그 중 가장 끝나는 시간이 느린 사람을 골라야 한다.
그 외의 경우에는 더 일찍 시작하는 대회여도 참가를 할 수 있기 때문에 이와 같은 구현이 필요하다.
그리고 값의 변경이 필요한 경우에 맵에 존재하는 값이 1인 경우에는 이 노드를 삭제해버리고 그렇지 않은 경우에는 이 값을 업데이트 한다.
그리고 끝나는 시간을 새로운 노드로 추가하던지 존재하는 값을 업데이트 한다.
주석
파이썬으로 문제를 풀려 했을 때는
1. 가지고 있는 딕셔너리의 키 값을 정렬한 후에 시작 시간 보다 작은 놈 중 가장 큰 걸 찾으려 했다. 근데 이럴 경우 시간이 매우 많이 소요되어서 포기 했다.
2. 정렬 없이 그냥 찾는 다면? 이라는 생각에서 했지만 당연히 시간이 많이 소요된다.
그래서 찾던 도중 다른 사람들이 multiset을 쓰는 것을 보았다. 입력된 값을 바로 정렬해서 가지고 있는 자료구조였다. 파이썬에서 이와 같은 자료구조가 없는 것 같아 친구와 같이 자바를 이용해서 해결했다.
이분 탐색을 통해 원소의 위치를 찾기에 훨씬 빠르고 정렬도 트리를 이용하기 때문에 빠르다고 한다.
파이썬 사용자들중 임의로 위의 자료구조를 제작해서 사용하는 사랆도 있는 것 같으니 추후에 이를 다시 공부해 보면 될 거 같다.
import java.io.*;
import java.util.*;
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;
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);
}
}
