k550706   3년 전

분리집합 없이 문제를 O(n^2)로 단순 브루트포스로 풀면 TLE 처리됩니다.

어떤 비행기 번호(a)가 들어오면 Greedy하게 a,a-1,a-2, ..... , 2,1을 순서대로 확인해야 하기 때문에 시간이 오래걸립니다.

이를 해결하기 위해서는 비행기 번호(a)가 들어와서 b번 게이트에 도킹시켰다면,

그 다음에 또 a번 비행기가 들어온다면 a,a-1,a-2 .... 2,1번의 게이트를 순서대로 확인하는 것 대신

a,a-1,a-2, ..... b,b-1,b-2, ..... 2,1에서

과감하게 a~b+1번까지의 게이트는 모두 검사할 필요없이 스킵하시면 됩니다.

즉 a번 비행기가 들어왔을때 최종적으로 도킹한 b번 게이트를 기록하고

이 다음에 다시 a번 비행기가 들어오면 b-1부터 도킹가능 여부를 확인한다면 직관적으로 문제를 풀수 있습니다.

최악의 경우를 가정하자면

10000개의 게이트를 가진 공항에 10000번 비행기가 10000개 들어올 경우에 단순 브루트포스 작업은 O(n^2)으로 처리해야 하나

최종 게이트를 기록하는 방식을 활용한다면 더 빠르게 처리 가능해서 AC 받을수 있습니다.

댓글을 작성하려면 로그인해야 합니다.