문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다.

이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

문제풀이

사용한 알고리즘 : Union-Find

잘 생각해보면 i번째 비행기가 1~g_i 게이트 중 하나에 도킹하려 할 때,

무조건 가능한 큰 게이트에 도킹한다고 생각해줍니다.

즉, i번째 비행기가 1~5 게이트 중 하나에 도킹하려 하고, 4,5번 게이트는 이미 도킹이 되었을 때, i번째 비행기는 3번 게이트에 도킹하게 됩니다.

이후 j번째 비행기가 1~3 게이트 중 하나에 도킹하려 하면 3-1 = 2번 게이트에 도킹 되겠죠?

1~x 게이트 중 하나에 도킹하려 하는 비행기가 도킹하게 되는 게이트를 리턴해주는 함수입니다.

(초기에는 모든 i 에 대해 자기 자신을 리턴합니다.)

과정(0)의 생각을 구현해주는 함수입니다.

1~x 게이트 중 하나에 도킹하려 할 때, 도킹하게 되는 게이트를 구하고, 해당 게이트를 사용 했으므로 다음 비행기는 (해당 게이트 - 1) 번째 게이트에 도킹 되야 함을 갱신해줍니다.

모든 비행기에 대해 게이트에 도킹 가능한지 여부를 체크해주고, 도킹 불가능할 경우 이전까지 도킹한 비행기 수가 답이 됩니다.