탑승구
내 풀이
- gate 개수(n)만큼 int[n+1] 그래프를 만들고 plane 최대값의 가장 바깥 쪽 부터 채우는 식으로 풀었다.
- 이런식으로 해서 앞으로 순차적으로 오면서 만약 plane이 정착할 수 있다면 break 하는 식으로 했다.
- O(N^2)
동빈북풀이
- 동빈북과 나는 둘 다 가장 큰 수를 확인하는 것에서 동일하나 나는 그 때부터 차례대로 앞으로 오면서 도킹이 가능한지 확인하는 방법. 동빈북은 그를 합집합을 이용해서 풀었다는 것이 훨씬 더 빠른 방법 같아.
- 이렇게 있다고 가정하고
- 비행기가 순서대로 들어오면 차례대로 도킹을 수행해야 하는데 가장 큰 번호의 탑승구로 도킹을 수행한다.
- 도킹하는 과정을 탑승구 간 합집합 union 연산을 이해하다.
- 새롭게 비행기가 도킹이 되면 해당 집합을 바로 왼쪽에 있는 집합과 합친다.
- 집합의 루트가 0이면 더 이상 도킹이 불가능 한 것으로 판단
spring, java학습