탑승구

 

 

 

문제

- G개의 공항 게이트 수가 주어진다.

- P개의 착륙 예정 비행기 수가 주어진다.

- 순차적으로 비행기가 착륙 가능한 탑승구의 범위가 주어진다.

- 이때 특정 비행기가 착륙가능한 게이트가 없을시 종료 시킨다.

 

예시

4, 1, 1 이 주어졌을 때

첫번째 비행기는 1~4 게이트에 착륙 가능하다.

두번째 비행기는 1번 게이트에만 착륙 가능하다.

세번째 비행기는 1번 게이트에만 착륙 가능하지만 두번째 비행기 또한 1번 게이트에만 착륙 가능하므로 종료 된다

결과적으로 최대 2개의 비행기만 착륙 가능하다.

 

 

 

아이디어

- 크루스칼을 "착륙 가능한 범위로 사용한다"

 

처음 문제를 풀 때, 리스트를 1부터 G까지 1로 설정하였다.

이 후, 예를 들어, 2가 들어오면 2에 위치한 리스트 값을 -1 해주었고

만약 또 2가 들어온다면 2에 위치한 리스트 값은 0이기에 착륙 불가능 판단하고

for문으로 1부터 줄여가면서 1인 지점에 착륙, 모두 0이면 착륙 완전 불가능을 판단했었다.

하지만 이 로직은 굉장히 효율적이지 못하다.

만약 10000이라고 쳤을 때, 10000부터 1까지 모두 확인을 해야한다. 시간 복잡도가 굉장히 증가한다.

 

 

크루스칼을 사용하면 좀 더 효율적으로 문제를 해결 가능하다.

처음에 10000이 들어오면 10000, 9999의 부모를 9999로 지정되고 다음으로 넘어간다.

다음에 10000이 들어오면 10000의 부모는 9999이고 9999, 9998의 부모를 9998로 지정한다.

연산의 수를 확줄일 수 있다.

또한, 만약, 1부터 1000까지 들어왔고 다음에 10000이 들어온다고 가정하면,

첫번째 로직은 0이 아닐때까지 모든 1000이하의 리스트를 참고해야한다.

하지만 크루스칼은 이미 경로 최적화를 통해 9999의 부모 노드는 1로 설정되어 있기에 한번의 연산으로 종료가 가능해진다.

 

하지만 두 로직의 원리는 같다. "부모가 0이면 착륙 불가능을 의미하고, 1이면 한대 가능,.... 을 의미한다"

 

 

코드

public static void main(String[] args){
    int g = 4;
    int p = 3;
    int result = 0;
    int[] parents = new int[g+1];
    for(int i=0; i<g+1; i++){
        parents[i] = i; 
    }
    int[] data = {2, 2, 3, 3, 4, 4};
    for(int i : data){
        int parent0 = find_paretns(parents, i);
        if(parents[i] == 0){
            break;
        }
        int parent1 = find_paretns(parents, parent0);
        int parent2 = find_paretns(parents, parent0-1);
        parents[parent1] = (parent1 > parent2) ? parent2 : parent1;   
        parents[parent2] = (parent1 > parent2) ? parent2 : parent1;
        result += 1;
    }

    System.out.println(result);
}
public static int find_paretns(int[] parents, int node){
    if(node != parents[node]){
        parents[node] = find_paretns(parents, parents[node]);
    }
    return parents[node];
}