* 정답 코드에 대한 설명이 있습니다. 아직 문제를 풀고 계신 분들은 참고 바랍니다.

https://www.acmicpc.net/source/23448700

위 코드가 틀린 이유를 알고 싶은 코드입니다.

T = 10, k = 1,000,000으로 고정해둔 뒤, 이후 연산은 랜덤으로 설정한 입력 데이터를 만들어 테스트를 여러 번 진행했습니다.

정답 코드(https://www.acmicpc.net/source/23447596)와 실행 결과를 비교했을 때, 둘의 결과는 같았습니다.

이후 새로운 입력 데이터를 만들어 테스트를 반복해도 둘의 결과는 같았습니다.

하지만, 틀린 코드로 답안을 제출하면 틀렸다는 결과가 나옵니다.

틀린 코드에서는 우선순위 큐를 이용하여 삭제한 최댓값, 최솟값을 저장합니다.

삽입 연산을 할 때는 최솟값을 저장하는 mQ와 최댓값을 저장하는 MQ에 각각 값을 push 합니다.

삭제한 최댓값을 저장하는 DeletedMax는 오름차순으로 정렬되며, 최솟값을 저장하는 mQ와 비교하여 pop을 진행합니다.

삭제한 최솟값을 저장하는 DeletedMin은 내림차순으로 정렬되며, 최댓값을 저장하는 MQ와 비교하여 pop을 진행합니다.

정답 코드에서는 맵을 이용하여 각 값을 key로 하고 그 개수를 value로 하여 활용합니다.

삽입 연산을 할 때는 mQ와 MQ에 각각 값을 push하고, 그 값을 key로 하는 value에 1을 더합니다.

삭제 연산을 할 때는 mQ(또는 MQ)의 top을 key로 하는 value가 0이면 pop을 반복하여 이미 삭제된 값을 반영합니다.

이후, mQ(또는 MQ)의 top을 key로 하는 value에 1을 뺀 다음 pop을 합니다.

깊이 생각을 해봐도, 위 둘의 방식만 다를 뿐이지 결과를 출력하는데 차이는 없는 것 같습니다.

틀린 코드에서도 삭제된 요소가 오름차순 또는 내림차순으로 정렬됨으로써 삭제할 요소가 누락되는 일도 없을 것이고요.

틀린 코드의 방식이 왜 틀렸는지 몇 시간을 고민해봤지만 모르겠습니다.