[99클럽 4기 코테 스터디 TIL 25일차 보너스문제] 이중우선순위큐 (feat. TreeMap)

1) 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

• 처음 PriorityQueue로 접근했는데,
• 최소힙과 최대힙을 동시에 설정하는 것이 어렵다 느껴 chatgpt의 도움을 받아 TreeMap 자료구조를 학습했다.

2) 내가 구현한 코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        TreeMap<Integer,Integer> tm = new TreeMap();
        
        for(int i=0; i<operations.length; i++){
            String operation =  operations[i].split(" ")[0];
            int num =  Integer.parseInt(operations[i].split(" ")[1]);           
            if(operation.equals("I")){                
                tm.put(num,num);
            }else if(operation.equals("D") && num == 1){//최댓값 삭제
                if(!tm.isEmpty())tm.remove(tm.lastKey());
            }if(operation.equals("D") && num == -1){//최솟값 삭제
                if(!tm.isEmpty())tm.remove(tm.firstKey());
            }
        }        
        
        if(!tm.isEmpty()){
             answer[0] = tm.lastKey(); //최댓값
            answer[1] = tm.firstKey(); //최솟값   
        }else{
            answer[0] = 0; 
            answer[1] = 0;   
        }
        
        
        return answer;
    }
}

 

3) TreeMap이 제공해주는 메서드 및 특징

0. TreeMap의 특징

• 정렬 기준: 키는 기본적으로 자연 순서(Comparable)로 정렬됩니다. 사용자 정의 정렬 기준(Comparator)도 설정할 수 있습니다.
• 시간 복잡도: 대부분의 메서드는 O(log n)의 시간 복잡도를 가집니다.
• 중복 키 허용: 중복 키를 허용하지 않으며, 동일한 키를 삽입하면 기존 값이 대체됩니다.

1. 데이터 조작 메서드

put(K key, V value)	지정된 키와 값을 삽입합니다. 이미 키가 존재하면 값을 업데이트합니다.
putAll(Map<? extends K, ? extends V> map)	주어진 맵의 모든 엔트리를 삽입합니다.
remove(Object key)	지정된 키에 해당하는 엔트리를 삭제하고, 삭제된 값을 반환합니다.
clear()	모든 데이터를 삭제합니다.
replace(K key, V value)	지정된 키가 존재할 경우 해당 값을 새 값으로 대체합니다.
replace(K key, V oldValue, V newValue)	지정된 키와 기존 값이 일치할 경우 새 값으로 대체합니다.
compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	키와 연관된 값을 재계산합니다.
computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)	키가 없을 경우 값을 계산하고 삽입합니다.
computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)	키가 있을 경우 값을 재계산하고 업데이트합니다.

2. 조회 메서드

get(Object key)	지정된 키에 해당하는 값을 반환합니다.
containsKey(Object key)	키가 존재하는지 여부를 반환합니다.
containsValue(Object value)	값이 존재하는지 여부를 반환합니다.
isEmpty()	맵이 비어 있는지 확인합니다.
size()	맵의 엔트리 수를 반환합니다.

3. 키 또는 값 정렬 메서드

firstKey()	맵의 가장 작은(첫 번째) 키를 반환합니다.
lastKey()	맵의 가장 큰(마지막) 키를 반환합니다.
headMap(K toKey)	지정된 키보다 작은 모든 키와 값을 포함하는 서브 맵을 반환합니다.
headMap(K toKey, boolean inclusive)	지정된 키보다 작거나 같은 키를 포함할지 여부를 설정하여 서브 맵을 반환합니다.
tailMap(K fromKey)	지정된 키보다 크거나 같은 모든 키와 값을 포함하는 서브 맵을 반환합니다.
tailMap(K fromKey, boolean inclusive)	지정된 키보다 크거나 같은 키를 포함할지 여부를 설정하여 서브 맵을 반환합니다.
subMap(K fromKey, K toKey)	지정된 키 범위 내의 모든 키와 값을 포함하는 서브 맵을 반환합니다.
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	시작 및 끝 키 포함 여부를 지정하여 서브 맵을 반환합니다.

4. 엔트리(키-값 쌍) 관리 메서드

entrySet()	맵의 모든 엔트리(키-값 쌍)를 포함하는 Set을 반환합니다.
keySet()	맵의 모든 키를 포함하는 Set을 반환합니다.
values()	맵의 모든 값을 포함하는 Collection을 반환합니다.
firstEntry()	맵의 가장 작은(첫 번째) 엔트리를 반환합니다.
lastEntry()	맵의 가장 큰(마지막) 엔트리를 반환합니다.
pollFirstEntry()	가장 작은(첫 번째) 엔트리를 제거하고 반환합니다.
pollLastEntry()	가장 큰(마지막) 엔트리를 제거하고 반환합니다.
descendingKeySet()	맵의 키를 역순으로 정렬하여 반환합니다.
descendingMap()	맵을 역순으로 정렬한 맵을 반환합니다.

5. 병렬 처리 및 탐색 관련 메서드

forEach(BiConsumer<? super K, ? super V> action)	각 엔트리에 대해 지정된 작업을 수행합니다.
merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)	키가 이미 있을 경우 값을 병합하거나 새 값을 삽입합니다.
navigableKeySet()	키를 정렬된 상태로 반환합니다.
descendingKeySet()	키를 역순으로 정렬된 상태로 반환합니다.