[Programmers] 이중우선순위큐 - Java

문제

프로그래머스

 

풀이

TreeMap을 사용한다. 

- TreeSet을 사용하면, 중복된 값이 나왔을 경우, 개수를 저장할 수 없는 문제가 있다.

key: 값

value: 값이 저장된 횟수를 저장하는 Map을 사용한다.

- 일반적인 Map을 사용하면, Key가 가장 작은 값 큰 값을 찾으려고하면, 모든 key 값을 순회해서 찾을 수 있다. 하지만 key값이 최대 100만개가 올 수 있다면, 시간초과가 발생하게된다.

 

=> key값을 삽입할때마다, 정렬해주면서, Map처럼 <key, value>쌍으로 저장할 수 있는 TreeMap을 사용해야한다.

 

TreeMap이나 TreeSet은 가장 작은 값을 구할 수 있지만, last(), lastKey()와 같은 메서드를 사용해서, 가장 큰 값도 동시에 구할 수 있다.

TreeMap 메서드

TreeSet 메서드

 

1. I 연산일때, TreeMap에 key: 값과 value: 값의 개수를 저장한다.

2. D 연산일때, 최댓값, 최솟값 삭제 여부에 따라서 적절한 key 값을 꺼내서, 개수를 가져온다.

2-1. 개수를 1을 감소했을때, 0이면 삭제(아예 없음), 0이 아니라면, key: 값, value: 값의 개수를 다시 넣는다(덮어쓴다)

3. TreeMap의 key가 비었는지 여부에 따라, 적절한 int 배열을 반환한다.

 

 

소스코드

import java.util.TreeMap;

class Solution {
    private static final String INSERT = "I";
    private static final String DELETE = "D";

    private static final long DELETE_MAX = 1;
    private static final long DELETE_MIN = -1;

    public int[] solution(String[] operations) {
        TreeMap<Integer, Integer> map = new TreeMap<>();

        for (String op : operations) {
            String[] s = op.split(" ");

            String command = s[0];
            int key = Integer.parseInt(s[1]);

            if (command.equals(INSERT)) {
                map.put(key, map.getOrDefault(key, 0) + 1);
            } else {
                //빈큐 데이터 삭제 명령시 무시
                if (map.keySet().isEmpty()) {
                    continue;
                }

                int target = -1;

                if (key == DELETE_MAX) {
                    target = map.lastKey();
                } else {
                    target = map.firstKey();
                }

                int cnt = map.get(target);
                cnt -= 1;

                if (cnt == 0) {
                    map.remove(target);
                } else {
                    map.put(target, cnt);
                }
            }
        }

        if (map.keySet().isEmpty()) {
            return new int[] {0, 0};
        }

        return new int[] {map.lastKey(), map.firstKey()};
    }
}

 

참고자료

https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html

https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html