오늘의 키워드
아침에 코드카타를 하는데, 최대 k명의 랭커만 유지를 시켜야하는 문제가 있었다.
보자마자 우선순위큐를 이용해서 풀어보고 싶었다.
물론 이 문제가 일정 수치 이내의 시간복잡도를 요구하진 않겠지만, 그냥 그러고 싶었다.
그런데 문제가 생겼다. 프로그래머스와 같은 코딩테스트 사이트들은 .Net 버전이 최신 버전이 아니어서 .Net 8.0 이상에서만 지원하는 PriorityQueue<T, T>를 사용할 수 없었다.
문제는 그냥 List와 Sort를 이용해서 풀긴 했지만, 만약 우선순위 큐를 써야만 하는 문제가 나온다면 어떻게 해야할까? 궁금해져서 튜터님께 질문해봤다. 내가 얻은 것들을 정리해보려한다.
코테에서 우선순위 큐를 꼭 써야한다면
C#에서는 SortedSet을 이용해서도 우선순위 큐를 비스무리하게 구현할 수 있다고 한다. 하지만 이 경우에는 원소의 중복이 허용이 되지 않기 때문에, 중복을 허용하게 element의 자료형을 가공해야한다.
아니면 직접 우선순위 큐를 구현해서 사용해야한다. 이건 미리 코드스니펫을 짜둬야 가능한 방법인 것 같다. 코테 시간도 촉박한데 이걸 구현하고 있을 수는 없으니까...
이건 내 생각인데, 그냥 이런 문제를 만나면 C++로 도망가자.
하지만 꼭 우선순위 큐로 풀지 않아도?
시간복잡도를 잘 계산하자. 대부분의 코딩테스트는 대략 2~3천만 번의 연산을 기준으로 잡는다고 한다.
.Net 버전에 따른 OrderBy vs Sort
우선순위 큐 대신 List로 알고리즘을 푼다고 하면, 정렬도 가벼운 녀석을 써야할 것 같아서 대표적인 정렬 메서드 중에 어떤 게 더 빠르고 가벼운지 알아야할 것 같았다.
Linq는 .Net 3.x에서 나온 기능이다. 초창기엔 Array.Sort가 더 빨랐다고 한다. 하지만 최신 버전(아마도 .Net 7.x인 것 같다.)의 Linq.OrderBy는 원소의 개수가 일정 수치 이상이면 Array.Sort보다 빠르다고 한다.
유니티는 최신 .Net을 지원하지 않는다.
때문에 Linq의 성능이 떨어질 수 있다.
원소의 개수가 어마무시하게 많은 게 아니라면, 쿼리적인 접근이 더 편리한 상황이 아니라면, 사용을 자제하는게 좋을 것 같다.
