목록2024/11/04 (1)
걸음마부터 달리기
[24/11/04] 우선순위 큐
우선순위 큐만 알면 쉽게 풀리는 문제이다.그러기에 우선순위 큐를 알아보자. 일반적인 큐는 FIFO의 구조로 오로지 들어간 순서에만 영향을 받는다. 따라서 이미 들어간 순간 내가 임의로 순서 조작을 하지는 못한다. 내가 어떤 순서로 큐로 넣었던 간에 큐 내부에서 우선순위를 정하여 다시 정렬하여 그 우선순위에 맞게 큐에서 순서대로 빼는 것을 우선순위 큐라고 한다. 따라서 해당 문제는 우선순위 큐가 없었다면 매번 뺄때마다 리스트 원소를 전부 보고 작은 순서대로 빼야되기에 이미 O(N)이 걸리고 그것을 n번 해야되기에 O(N^2)이 걸려 타임아웃이다.그러면 우선순위 큐에서 우선순위를 어떻게 지정할것이냐? 우선순위 큐에서는 우선순위가 높은 것을 차례로 poll 시킨다.Comparator 를 통해서 임의적으로 순서..
카테고리 없음
2024. 11. 4. 23:00