백준 #16566 - 카드 게임

AnonymousBlueCat·2023년 2월 17일
0

백준

목록 보기
8/12

첫 시도


민수가 지는 경우는 고려하지 않아도 되기 때문에, 철수가 낸 카드보다 높은 카드 중 가장 낮은 카드를 bisect 라이브러리를 활용한 이진 탐색으로 구한다. 그리고 사용한 민수의 카드는 del()을 활용하여 제거한다. 이를 반복한다.

결과는 당연하게도 TLE

두 번째 시도

사실 del을 사용하면서도 되게 찜찜했다. 시간복잡도가 O(n)인 del을 사용하면 답은 간단히 구할 수 있더라도 시간 초과가 나기 쉽상이다. 리스트에 원소를 삭제하는 방법 대신 다른 알고리즘을 사용해야 한다.

분리 집합

분리 집합이 바로 그 답이었다. 이미 사용한 카드는 그보다 높은 카드의 집합에 속하도록 하면, 집합 내에서 가장 높은 카드와 그 다음 집합에서 가장 높은 카드, 이런 식으로 비교하면 되기 때문이다. 시간복잡도를 줄이기 위해 리스트의 원소 삭제 대신 사용하면 되는 거라서 상당히 다양한 문제에서 활용 가능한 테크닉일 것 같다. 그 외에는 아무 문제 없이 구현하면 끝.

문제


https://www.acmicpc.net/problem/16566

profile
알고리즘 온라인 공부 노트

0개의 댓글