이번에는 프로그래머스 이중우선순위큐 문제를 풀었다.
숫자를 삽입하고, 명령에 따라 최댓값이나 최솟값을 삭제한 뒤 마지막에 남은 최댓값과 최솟값을 반환하는 문제였다. 일반 우선순위 큐 하나만 사용하면 한쪽 끝은 쉽게 꺼낼 수 있지만 반대쪽 끝을 처리하기가 불편했다.
TreeSet 기반 최솟값과 최댓값 접근
구현에서는 정렬 상태를 유지하는 TreeSet을 사용했다.
I 숫자: 값을 삽입D 1:pollLast()로 최댓값 삭제D -1:pollFirst()로 최솟값 삭제
삭제 명령이 들어왔을 때 Set이 비어 있으면 해당 연산을 건너뛰었다. 모든 명령을 처리한 뒤 값이 하나만 남으면 같은 값을 최댓값과 최솟값에 넣고, 두 개 이상이면 양 끝 값을 각각 꺼냈다.
각 삽입과 삭제는 O(log n)이고, 전체 명령 수를 n이라고 하면 시간 복잡도는 O(n log n)이다. 정렬된 값을 저장하므로 공간 복잡도는 O(n)이다.
중복 값 처리를 위한 자료구조 선택 기준
이번 커밋의 구현은 TreeSet<Integer>를 사용했다. TreeSet은 같은 값을 여러 번 넣어도 하나만 보관한다.
문제 조건에서는 같은 최댓값이나 최솟값이 여러 개라면 그중 하나만 삭제해야 한다. 따라서 입력에 중복 값이 중요한 경우에는 값별 개수를 함께 저장하는 TreeMap<Integer, Integer>나 두 개의 우선순위 큐와 지연 삭제 방식을 사용하는 편이 더 일반적이다.
현재 제출 기록은 정확성 100점, 실행 시간 35.55ms, 메모리 134MB였다. 제출 결과와 별개로 자료구조가 중복 개수를 보존하지 않는 경계는 이후 비슷한 문제를 풀 때 다시 확인할 부분으로 남겼다.
아는거 없는 전공자