문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 정렬, 우선순위 큐
당신은 친구를 도와 새로운 카풀 앱을 개발해야 한다. 그 중 운전자와 승객을 매칭 시켜주는 알고리즘을 당신이 개발해야 한다. 현재 이 앱은 베타 버전이기 때문에 동-서로 길게 늘어진 고속도로 위에 위치한 지역에서만 서비스를 하고 있으며 아래와 같은 제한이 있다.
- 모든 운전자와 승객은 가장 동쪽에 위치한 “출발지" 도시에서 출발한다.
- 총 N명의 승객이 있으며, i번째 승객은 출발지에서 서쪽으로 xi 미터 떨어진 곳에 위치한 목적지에 가고 싶어한다 (0 < xi).
- 총 M명의 운전자가 있으며, j번째 운전자는 출발지에서 서쪽으로 yj 미터 이상 zj 미터 이하 떨어진 곳 사이에 가고 싶어하는 승객을 최대 한 명 태워줄 의향이 있다 (0 < yj ≤ zj).
당신은 이 조건들을 만족하면서 최대한 많은 승객-운전자를 매칭시키는 알고리즘을 작성해야 한다.
예를 들어, 3명의 승객과 3명의 운전자가 있을 때, x, y, z 값이 아래와 같다고 하자.
- x = [10, 20, 30]
- y = [8, 2, 25]
- z = [8, 18, 35]
이 경우 승객 1, 2, 3은 각각 정확 10미터, 20미터, 30미터 떨어진 곳으로 가고 싶어하며, 운전자 1은 정확히 8미터 떨어진 곳에 가려는 승객을 태울 의향이 있고, 운전자 2는 2미터 이상 18미터 이하 떨어진 곳에 가려는 승객을 태울 의향이 있고, 운전자 3은 25미터 이상 35미터 이하 떨어진 곳에 가려는 승객을 태울 의향이 있다.
이 경우, 승객1-운전자2, 승객3-운전자3을 매칭시켜주면 총 두 쌍을 매칭시킬 수 있고 이보다 많은 수의 승객-운전자를 매칭 시킬 수 있는 방법은 없다.
입력으로 N, M, 그리고 x, y, z 값들을 입력 받아 최대한 많은 승객-운전자 쌍을 매칭시키면 몇 쌍을 매칭 시킬 수 있는지 계산하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 10).
각 테스트 케이스의 첫 줄에는 N, M 이 주어진다.
그 다음 줄에 xi 가 공백으로 구분되어 주어진다 (1 ≤ xi ≤ 1,000,000,000).
다음 M줄에 걸쳐 각 줄에 yj 와 zj 가 공백으로 구분되어 주어진다 (1 ≤ yj ≤ zj ≤ 1,000,000,000).
출력
각 테스트 케이스에 대해, 최대한 많은 승객-운전자를 매칭 시켰을 때 몇 쌍을 매칭시킬 수 있는지 출력한다.
풀이
승객-운전자를 매칭 시켰을 때 최대 몇 쌍을 매칭시킬 수 있는지 출력해야 한다.
특정 승객이 있을 때
이 승객을 태울 수 있는 운전자가 여려 명 있다고 생각해 보자,
이때 어떤 운전자와 매칭을 시키는 게 최적일까?
답은 z가 가장 작은 운전자와 매칭 시키는 것이 최선이 된다.
왜냐하면 일단 승객을 태울 수 있다고 했을 때는 운전자들의 y는 신경쓰지 않아도 된다.
z만 보면 된다. z가 상대적으로 더 큰 운전자와 매칭한다면 큰 z - 그보다 작은 z 만큼의 승객을 태울 수 있는 범위를 잃게 된다.
그래서 승객을 태울 수 있는 기회비용을 최대한 크게하기 위해서는 결국 가장 작은 z를 매칭해야 한다는 결론에 도달한다.
이제 구현 아이디어를 생각해야 하는데, 어렵지 않다.
승객의 x를 기준으로 승객을 오름차순으로 정렬하고,
운전자는 y를 기준으로 운전자를 오름차순 정렬한다.
먼저, x가 작은 순으로 탐색을 시작한다.
x가 있을 때 이 승객과 매칭 가능성이 있는 모든 운전자를 모아본다. 여기서 가능성이 있는 이라고 하는 이유는 z에 따라서 불가능할 수도 있기 때문이다.
매칭 가능성이 있다는 의미는 x보다 운전자의 y가 작거나 같은 운전자를 의미한다.
그리고 그러한 운전자 중에서 y가 가장 작은 운전자와 매칭하는 것이 최선이기 때문에 운전자들은 z순으로 오름차순 정렬되는 우선 순위 큐에 넣는다.
그러면 우선 순위 큐에는 매칭 가능성이 있는 운전자들이 모여있게 되고, z를 기준으로 오름차순 정렬이 되기 때문에 최적이 될 수 있는 순으로 운전자들은 정렬이 될 것이다.
여기서 poll()하고 매칭해주는 것이 아닌 z와 x관계를 봐야한다. x는 z보다 작거나 같아야 y <= x <= z를 최종적으로 만족하기 때문이다.
그래서 만족하지 않는다면 그냥 버리면 되고, 만족한다면, 현재 승객과 poll()하고 조건을 만족한 운전자와 매칭하고, 다음 승객을 탐색하면 된다.
이런 방식으로 모든 승객을 탐색한다면, 승객-운전자의 최대 쌍을 구할 수 있다.
이 풀이의 시간 복잡도는 Math.max(O(MlogM), O(NlogN)이 된다.
소스 코드
import java.io.*;
import java.util.*;
class Driver implements Comparable<Driver> {
int y, z;
Driver(int y, int z) {
this.y = y;
this.z = z;
}
@Override
public int compareTo(Driver o) {
if(this.z < o.z) {
return -1;
} else if(this.z > o.z) {
return 1;
}
return 0;
}
}
public class Main {
static int T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int t=0; t<T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //승객의 수
int M = Integer.parseInt(st.nextToken()); //운전사의 수
int[] pArr = new int[N]; //승객 배열
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
pArr[i] = Integer.parseInt(st2.nextToken());
}
Arrays.sort(pArr); //승객을 오름차순으로 정렬한다. x기준
Driver[] dArr = new Driver[M];
for(int i=0; i<M; i++) {
StringTokenizer st3 = new StringTokenizer(br.readLine());
int y = Integer.parseInt(st3.nextToken());
int z = Integer.parseInt(st3.nextToken());
dArr[i] = new Driver(y, z);
}
Arrays.sort(dArr, new Comparator<Driver>() {
//y를 기준으로 오름차순한다.
@Override
public int compare(Driver d1, Driver d2) {
if(d1.y < d2.y) {
return -1;
} else if(d1.y > d2.y) {
return 1;
}
return 0;
}
});
int answer = 0;
PriorityQueue<Driver> pq = new PriorityQueue<>();
int dArrCursor = 0;
for(int i=0; i<N; i++) {
while(dArrCursor < M) {
if(pArr[i] < dArr[dArrCursor].y) {
break;
}
pq.add(dArr[dArrCursor]);
dArrCursor += 1;
}
// pq에는 승객을 태울 수 있는 운전자 객체가 들어가있다.
//그런데 z를 추가적으로 확인해야한다.
//최적의 운전자를 하나 매칭해 준다.
while(!pq.isEmpty()) {
Driver d = pq.poll();
if(pArr[i] <= d.z) {
//매칭 지점
answer += 1;
break;
}
}
}
sb.append(answer).append("\n");
}
System.out.println(sb.toString().trim());
}
}