https://www.acmicpc.net/problem/10775
박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
생일 선물로 공항을 사주는 친구 어디 없나...
공항의 게이트에 비행기를 도킹하는데 만약 도킹할 수 있는 게이트가 없다면 공항은 폐쇄된다.
모든 게이트에 대해 boolean 배열을 만들어 비행기가 도킹하면 해당 인덱스를 true로 만드는 것을 통해 문제를 풀 수 있다. 하지만 입력값이 크기때문에 n^2의 방법으로는 시간 초과에 직면한다.
문제의 분류에 분리 집합. 즉, 유니온-파인드 알고리즘을 사용하면 시간내에 풀 수 있다.
비행기가 특정 게이트에 도킹이 성공했다면 다음 같은 번호 비행기는 성공한 게이트보다 1작은 번호의 게이트에 도킹할 수 있다. 즉 1작은 번호의 게이트와 도킹에 성공한 게이트를 하나의 집합으로 묶으면 비행기가 다음 도킹해야할 위치를 지정해 줄 수 있다.
게이트 번호가 1부터 시작하기때문에 find(num)을 통해 구한 값이 0보다 크다면 유니온을 통해 집합으로 묶어 주고 만약 find(num)의 값이 0이라면 모든 게이트가 꽉찬 것이기 때문에 공항이 폐쇄되고 종료하면 된다.
import java.io.*;
import java.util.Arrays;
public class Main {
static int n, m, k;
static int[] rank;
static int[] pa;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
int p = Integer.parseInt(br.readLine());
pa = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++)
pa[i] = i;
int cnt = 0;
for (int i = 0; i < p; i++) {
int num = Integer.parseInt(br.readLine());
int k = find(num);
if(k > 0) {
union(k - 1, num);
cnt++;
}
if(k == 0)
break;
}
bw.write(cnt + "\n");
bw.flush();
bw.close();
br.close();
}
private static void union(int a, int b) {
int aRoot = find(a);
int bRoot = find(b);
if (aRoot != bRoot) {
if (aRoot == pa[aRoot])
pa[bRoot] = aRoot;
else
pa[aRoot] = bRoot;
}
}
static int find(int a) {
if (pa[a] < 0 || pa[a] == a) {
return a;
} else {
int y = find(pa[a]);
pa[a] = y;
return y;
}
}
}