일반적인 우선순위 큐에서 tail에서도 값이 나올 수 있게 만드는 문제이다. I + (숫자)인 경우 숫자를 삽입하는 것이고 "D 1"인 경우 최댓값을 제거하고, "D -1"이라면 최솟값을 제거한다. 이런 명령어들이 담긴 배열을 전부 수행하였을 때, 큐에 남은 최댓값과 최솟값을 배열로 담아 반환하면 된다. 문제링크
가장 쉬운 구현방법을 생각해보면 리스트를 선언하여 연산할 수 있겠지만, 그런 경우 시간이 굉장히 오래걸린다. 그래서 우선순위큐를 활용하여 문제를 풀어보자.
문제점은 우선순위큐에는 tail이라는 개념이 없는 것이다. 애초에 heap으로 구성이 되어 있으니 최대값만 찾거나 최소값만 찾을 수 있다. 필자는 이를 보완하기 위해 우선순위 큐 두개를 활용하기로 했다.
여기에 추가로 두 개의 맵을 선언하는데 맵의 역할은 각 큐에서 어느 숫자가 몇 번 삭제 되었는지 기록하는 용도이다. 우선순위 큐를 두개를 사용하였지만, 실제로는 하나의 큐로 인식하기 때문에 이 두 큐에서 한쪽만 원소가 삭제되면 안된다. 따라서 이 두 큐를 동기화하기 위해 사용된다.
첫 번째 for문을 보자. 일단 최대값을 제거해야 하는 경우 big에서 하나를 제거하고 맵에 삭제된 횟수를 갱신한다. 최솟값을 제거하는 경우도 동일한 원리로 작동한다.
만약 숫자를 삽입하는 경우라면 두 큐에 모두 삽입한다.
삭제 또는 추가를 마칠 때 마다, 동기화를 해야하는데 필자는 이를 synchronize라는 함수를 통해 구현하였다. 함수 내부를 들여다보면, 두 개의 while문이 나타나는데, 두 while문은 동작하는 방식이 동일하므로 첫번째 while문에 대해서 이야기하겠다.
big큐의 가장 첫번째 원소가 삭제된 횟수가 small에서 삭제된 횟수보다 작다면, 이는 지워야 하는 원소이므로 제거한다. big이 비어있지 않는 한 계속 반복하면 된다. 이를 통해 두 큐를 동기화 할 수 있다.
operation의 크기를 n이라 하였을 때, 최종 시간복잡도는 이다. 그거보다 시간복잡도가 높지 않을까 생각하는 분이 계실 수도 있는데, 생각해보면 두 큐에 들어갔다 나오는 횟수를 전부 더하면 이다.
테스트
질문하기를 보니까 조건에 부합하지 않게 짜도 통과되는 경우가 있다고 한다. 이 부분에서 좀 더 신경을 써줬으면 좋겠다.