더 맵게

import java.util.*;
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
 
        for (int s : scoville) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
 
        while (map.firstKey() < K) {
            if (map.size() < 2) {
                answer = -1;
                break;
            }
            int a = map.firstKey();
            // 해당 스코빌 지수가 여러 개일 경우 처리
            int b = map.get(map.firstKey()) > 1 ? map.firstKey() : map.higherKey(map.firstKey());
            int n = a + b * 2;
            // 해당 스코빌 지수가 없어지는 경우 처리
            if (map.get(a) > 1)
                map.put(a, map.get(a) - 1);
            else
                map.remove(a);
            if (map.get(b) > 1)
                map.put(b, map.get(b) - 1);
            else
                map.remove(b);
            map.put(n, map.getOrDefault(n, 0) + 1);
            answer++;
        }
        return answer;
    }
}

기존에는 ArrayList를 사용했었다.

하지만 문제에서 코드의 효율성을 판단했기에 데이터를 삽입했을 때 자동으로 오름차순 정렬해주는 TreeMap을 사용하였다.

Map의 특성상 중복된 Key는 들어갈 수 없어서 Value를 늘려주는 방식으로 사용했다.

index를 통해 값을 받을 수 없는 Map에서도 map.firstKey, map.lastKey를 통해 첫 번째 키와 마지막 키를 가져오는 방법이 존재했다.

이를 응용한 map.higherKey로 두 번째로 작은 키를 가져왔다.

 

다른 사람의 풀이를 보니 대부분의 사람들이 PriorityQueue를 사용하고 있었고 이 역시 자동으로 오름차순 정렬해주는 기능이 있었다.

PriorityQueue는 중복된 값을 저장할 수 있었기 때문에 더 좋은 방법이라고 생각한다.