문제 해결 전략
-
문제의 내용대로 pq 2개를 만들어서 진행하려고 하는데,
이렇게 되면, 한쪽pq에서만 pop해서 제거하려는 전략인데, -
문제가 한쪽에서만 꺼냈기 때문에 pq에 남아있는 ,쓸모 없는 정보에 대한 처리를 명확히 할 수 가 없다.
- 다른 방법이 없을까?? 를 생각해야 한다.
힌트
1) 문제를 읽으면서, 매번 삽입할때 마다 sort를 하는것은 아닌것 같고,
자동으로 정렬
2) 중복된 값을 허용하고 있다.
=> multiset을 생각해야 함.
multiset으로 접근하자.
알아야할 이터레이터
-
begin(), end()는 당연히 알고 있는거고,
-
next와 prev를 알아야함.
여기서는 맨끝부분에 prev 사용
- end는 마지막 원소값이 아니다!
🔥🔥🔥