민수가 지는 경우는 고려하지 않아도 되기 때문에, 철수가 낸 카드보다 높은 카드 중 가장 낮은 카드를 bisect 라이브러리를 활용한 이진 탐색으로 구한다. 그리고 사용한 민수의 카드는 del()을 활용하여 제거한다. 이를 반복한다.
결과는 당연하게도 TLE
사실 del을 사용하면서도 되게 찜찜했다. 시간복잡도가 O(n)인 del을 사용하면 답은 간단히 구할 수 있더라도 시간 초과가 나기 쉽상이다. 리스트에 원소를 삭제하는 방법 대신 다른 알고리즘을 사용해야 한다.
분리 집합이 바로 그 답이었다. 이미 사용한 카드는 그보다 높은 카드의 집합에 속하도록 하면, 집합 내에서 가장 높은 카드와 그 다음 집합에서 가장 높은 카드, 이런 식으로 비교하면 되기 때문이다. 시간복잡도를 줄이기 위해 리스트의 원소 삭제 대신 사용하면 되는 거라서 상당히 다양한 문제에서 활용 가능한 테크닉일 것 같다. 그 외에는 아무 문제 없이 구현하면 끝.