(c++) 최소 힙 구현 시, 비교 함수 대신 greater<>() 쓰기
- 7662 (이중 우선순위 큐)
- 셋으로 풀이했다면 우선순위 큐 풀이 힌트 주기 (최소 힙, 최대 힙이 필요하고, 서로 어떤 데이터가 삭제되었는지 체크할 컨테이너도 필요)
- 데이터 삭제 체크 컨테이너가 필요한 이유는, 최소 힙과 최대 힙을 서로 왔다 갔다하며 사용하면 시간초과남
- 체크 컨테이너 전역으로 선언했다면 매번 테스트 케이스마다 초기화 해줘야 함을 주의
- 5397 (키로거)
- deque의 중간 원소를 erase, insert하는 것은 O(N)의 시간복잡도가 걸리기 때문에, 커서를 기준으로 왼쪽 오른쪽을 나눠서 deque의 앞과 뒤에서만 연산(시간복잡도 O(1))이 일어나도록 하는 풀이 유도
- 2075 (N번째 큰 수)
- 메모리 제한이 있기 때문에, 모든 수를 저장하지 않고 상위 N개의 값만 저장하여 풀어야 함
- 최소힙 써야함을 잘 파악해야 함
- 13975 (파일 합치기 3)
- 14235 (크리스마스 선물)
- 12018 (Yonsei TOTO)
- 여러가지 풀이가 가능. L번째 큰 마일리지 계산 부분, 가장 많은 수업 듣기 계산 부분 이렇게 2가지로 나눈 다 했을 때 두 부분을 (우선순위큐+우선순위큐, 벡터(정렬)+우선순위 큐, 벡터(정렬)+벡터(정렬)) 로 풀이 가능
- 19640 (화장실의 규칙)
- 큐를 활용해서 줄 관리 해야 함
- 그 후, 줄의 앞에 있는 사람들은 우선순위 큐에 넣어서 관리