탑승구

이 문제는 도저히 어떻게 풀어야할지 감이 잡히지 않아서 풀지 못했다. 아이디어 부분에서 막힌 문제. 문제 자체는 쉽지만, 문제 조건을 보면 탑승구의 개수가 최대 10만개, 그리고 비행기의 개수가 최대 10만개라서 단순히 반복문을 통해 구현하면 무조건 시간초과가 뜨는 문제이다. 그래서 어떻게 해결해야할지 감을 잡지 못해 풀지 못했다. 풀이 이 문제는 서로소 집합 알고리즘을 사용해서 푸는 문제다. 각 탑승구를 서로 다른 집합으로 나타낸다고 해보자. 전체 탑승구가 4개일 때, 루트 0 1 2 3 4 탑승구 0 1 2 3 4 초기 상태에는 모두 루트 노드로 자기 자신을 가리키고 있다고 가정한다. 0번 탑승구는 존재하지 않지만, 문제 해결을 위해 0번 탑승구도 그려준다. 이 때, 비행기가 순서대로 들어오면 차례대..