문제
https://www.acmicpc.net/problem/10775
오늘은 신승원의 생일이다.
박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?
입력
첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.
두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.
이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.
출력
승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.
예제 입력 1
4
3
4
1
1
예제 출력 1
2
예제 입력 2
4
6
2
2
3
3
4
4
예제 출력 2
3
접근
이 문제는 예전에 몇 번 풀려고 시도했었다가 감을 못 잡겠어서 북마크만 해두고 짱박아둔 문제이다.
업보 청산을 하려고 다시 꺼내봤다.
근데 지금 다시 보니 너무 그리디 문제인데 예전에는 왜 전혀 못 풀었던 거지...
비행기가 순서대로 도착하고, 순서에 맞춰 도착한 비행기는 반드시 도킹을 해야만 한다.
그러니까 현재 도착해 있는 비행기에 대해서는 지금 상황에서의 최선의 선택을 할 수밖에 없다.
그렇다면 최선의 선택이란 뭘까?
1번부터 gi 게이트 중 하나를 선택해야 하기 때문에 당연히 gi 값이 작으면 선택 가능한 범위가 줄어들고, 이 값이 크면 범위가 늘어난다.
그렇다면 당연히, gi 값이 비교적 큰 비행기가 할 수 있는 한 큰 수의 게이트를 선택해야 gi 값이 비교적 작은 비행기들의 자리도 남아 있을 가능성이 높지 않을까?
즉, 최선의 방법은 gi보다 작거나 같은 게이트 중 아직 도킹되지 않은 최대한 큰 수의 게이트를 선택하는 것이 됨을 알 수 있다.
구현
1차 시도 (시간 초과)
예를 들어 gi 값이 5라면,
5번 게이트부터 1번 게이트까지 역순으로 순회하다가 아직 도킹되지 않은 게이트를 발견하면 순회를 중지하고 해당 게이트에 도킹하면 될 것이다. 1번 게이트까지 확인했는데 도킹할 수 있는 게이트가 없다면 공항을 폐쇄시키면 된다.
그래서 다음과 같이 구현을 했다.
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int G = Integer.parseInt(br.readLine());
int P = Integer.parseInt(br.readLine());
boolean[] gate = new boolean [G + 1];
int result = 0;
for (int n = 1; n <= P; n++) {
int flight = Integer.parseInt(br.readLine());
if (result > 0) {
continue;
}
for (; flight > 0; flight--) {
if (!gate[flight]) {
gate[flight] = true;
break;
}
}
if (flight == 0) {
result = n - 1;
}
}
if (result == 0) {
result = P;
}
System.out.println(result);
}
}골드 2인데 이렇게 쉬울 수 있나...? 그리디로 안 풀리는 반례가 있나? 하고 찾아보다가 못 찾겠어서 틀릴 걸 각오하고 채점을 돌려봤는데, 놀랍게도 틀리지 않고 70%대에서 시간 초과가 났다.
이 코드는 2중 for문으로 동작하기 때문에 최악의 경우 시간 복잡도가 O(P*G)일 것이다.
친구에게 배운 야매로 시간 초과 판별하는 방법을 써봤다.
컴퓨터가 대략 1초에 1억 번의 연산을 한다고 가정해보는 거.
이 문제의 시간 제한은 1초이므로 1억 번, 즉 10^8번의 연산을 할 수 있다고 해보자.
P와 G의 최댓값이 모두 10^5이므로 P*G의 최댓값은 10^10가 된다.
즉, 최악의 경우엔 시간 초과가 날 수도 있음을 대략적으로 직감할 수 있다.
외부 for문은 입력을 받으려면 반드시 필요하고, 선형 탐색을 하는 내부 for문의 시간 복잡도를 O(G) 미만으로 최적화 시켜야 통과하겠다는 결론이 나왔다.
역시 괜히 골드 2가 아니었다...
최종 풀이 (Union-Find 사용)
더 이상 생각나는 최적화 방법이 없어서 아이디어를 참고했다.
이렇게 가능한 가장 큰 자원을 사용하는 배치 문제는 서로소 집합, 즉 유니온 파인드(Union-Find)를 응용해서 풀 수 있는 대표적인 문제라고 한다...
- 각 게이트를 서로소 집합의 대표 노드로 둔다.
- gi번 비행기가 오면, gi 이하의 가장 가까운 사용 가능한 게이트를 찾아(find) 도킹한다.
- 도킹 후에는 그 게이트보다 1 작은 게이트와 병합(union)한다.
-> 현재 게이트는 이제 더 이상 사용할 수 없으니 다음번에는 자신보다 작은 게이트 중 사용 가능한 가장 큰 게이트로 배치하게 된다.
이렇게 하면 부모 링크의 정보를 갱신해가며 활용하기 때문에 탐색 중복을 없앨 수 있는 것이다.
import java.io.*;
class Main {
static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int G = Integer.parseInt(br.readLine());
int P = Integer.parseInt(br.readLine());
int result = 0;
parent = new int[G + 1];
for (int i = 1; i <= G; i++) {
parent[i] = i;
}
for (int i = 1; i <= P; i++) {
int gi = Integer.parseInt(br.readLine());
// 이미 공항이 폐쇄된 경우
if (result > 0) {
continue;
}
// 도킹시킬 수 있는 가장 큰 게이트를 찾기.
int dockingStation = find(gi);
// 더 이상 도킹 불가 -> 공항 폐쇄
if (dockingStation == 0) {
result = i - 1;
} else {
// 사용한 현재 게이트를 더 작은 쪽으로 병합.
union(dockingStation, dockingStation - 1);
}
}
// for문 빠져나온 후에도 result 값의 갱신이 이뤄지지 않음(== 공항이 폐쇄되지 않음)
// -> 모든 비행기를 도킹시킬 수 있다는 뜻.
if (result == 0) {
result = P;
}
System.out.println(result);
}
private static int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
parent[a] = b;
}
}
