99클럽 코테 스터디 9일차 TIL - 힙

문제

Relative Ranks

풀이

• HashMap 사용
  • int 배열 중 가장 높은 순위 1, 2, 3을 각각 string으로 맵핑해야 한다.
  • 3위 밖은 차례대로 rank 값으로 치환해줘야 함
  • Gold, Silver, Bronze의 Enum과 rank를 기록한 HashMap을 사용
  • rank(최대 3위) 안의 rank는 Enum을 사용하여 medal로 변환, 그 외는 차례대로 rank로 치환
• Max Heap 사용
  • heap 구현 후 int 배열을 heap에 insert
  • for문을 순회하며 heap에서 delete하고 answer에 차례대로 저장

코드 HashMap

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

class Solution {    
    public String[] findRelativeRanks(int[] score) {
        int maxRank = 3;
        
        int[] copiedScore = Arrays.copyOf(score, score.length);  
        
        Arrays.sort(copiedScore);
        
        int[] reversedSorted = reverse(copiedScore);
        
        Map<Integer, Integer> rankMap = getRankMap(reversedSorted);
        
        String[] answer = new String[score.length];
        
        for(int i = 0; i < score.length; i++){
            Integer rank = rankMap.get(score[i]);
            
            if(rank < maxRank){
               answer[i] =  Medal.getMedalByIndex(rank).getMedal();
            } else {
               answer[i] = String.valueOf(rank + 1);
            }
        }
        
        
        return answer;
    }
    

    public static int[] reverse(int[] array){
        int length = array.length;
        int[] reversedArray = new int[length];
        
        for(int i = 0; i < length; i++){
            reversedArray[length - i - 1] = array[i];
        }
        
        return reversedArray;
    }
    
    public static Map<Integer, Integer> getRankMap(int[] array){
        Map<Integer, Integer> rankMap = new HashMap<>();
        
        for(int i = 0; i < array.length; i++){
            rankMap.put(array[i], i);
        }
        return rankMap;
    }
    
        
    public enum Medal {
        GOLD("Gold Medal"), 
        SILVER("Silver Medal"), 
        BRONZE("Bronze Medal");
        
        private final String medal;

        Medal(String medal){
            this.medal = medal;
        }

        public String getMedal(){
            return medal;
        }

        public static Medal getMedalByIndex(int index){
            switch(index){
                case 0:
                    return GOLD;
                case 1:
                    return SILVER;
                case 2:
                    return BRONZE;
                default:
                    throw new IllegalArgumentException("존재하지 않은 순위" + index);
            }
        }
    
    }

}

코드 Max Heap

class Solution {    
    public String[] findRelativeRanks(int[] score) {
        MaxHeap myHeap = new MaxHeap();
        String[] answer = new String[score.length];
        
        for(int i = 0; i < score.length; i++){
            myHeap.insert(score[i], i);
        }
        
        for(int i = 0; i < score.length; i++){
            Node node = myHeap.delete();
            
            if(i < 3){
              answer[node.index] = Medal.getMedalByIndex(i).getMedal();
            } else {
              answer[node.index] = String.valueOf(i + 1);
            }
        }
        
        return answer;
    }
        
    public enum Medal {
        GOLD("Gold Medal"), 
        SILVER("Silver Medal"), 
        BRONZE("Bronze Medal");
        
        private final String medal;

        Medal(String medal){
            this.medal = medal;
        }

        public String getMedal(){
            return medal;
        }

        public static Medal getMedalByIndex(int index){
            switch(index){
                case 0:
                    return GOLD;
                case 1:
                    return SILVER;
                case 2:
                    return BRONZE;
                default:
                    throw new IllegalArgumentException("존재하지 않은 순위" + index);
            }
        }
    
    }
}
        
class Node {
    int value;
    int index;

    Node(int value, int index){
        this.value = value;
        this.index = index;
    }
}

class MaxHeap {
    private List<Node> heap;
    
    public MaxHeap(){
        this.heap = new ArrayList<>();
    }
    
    private int getLeftChildIndex(int parentIndex) {
        return parentIndex * 2 + 1;
    }

    private int getRightChildIndex(int parentIndex) {
        return parentIndex * 2 + 2;
    }
    
    private int getParentIndex(int childIndex) {
        return (childIndex - 1) / 2;
    }
    
    private Node peek(){
        return heap.isEmpty() ? null : heap.get(0);
    }
    
    private boolean hasParent(int index) {
        return getParentIndex(index) >= 0;
    }
    
    public int size(){
        return heap.size();
    }
    
    public void insert(int value, int index){
        Node node = new Node(value, index);
        heap.add(node);
        heapifyUp();
    }
    
    private void swap(int index1, int index2){
        Node temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }
    
    private void heapifyUp() {
        int currentIndex = heap.size() - 1;
        
        while(hasParent(currentIndex)){
            int parentIndex = getParentIndex(currentIndex);
            if(heap.get(parentIndex).value < heap.get(currentIndex).value){
                swap(parentIndex, currentIndex);
                currentIndex = parentIndex;
            } else {
                break;
            }
        }
    }
    
    public Node delete(){
        if(heap.isEmpty()){
            return null;
        }
        
        Node max = heap.get(0);
        Node last = heap.remove(heap.size() - 1);
        
        if (!heap.isEmpty()) {
            heap.set(0, last);
            heapifyDown();
        }
        
        return max;
    }
    
    private void heapifyDown(){
        int currentIndex = 0;
        int count = heap.size();
        
        while(true){
            int leftChildIndex = getLeftChildIndex(currentIndex);
            int rightChildIndex = getRightChildIndex(currentIndex);
            int largestIndex = currentIndex;
            
            if(leftChildIndex < count && heap.get(leftChildIndex).value >  heap.get(largestIndex).value){
                largestIndex = leftChildIndex;
            }
            
            if (rightChildIndex < count && heap.get(rightChildIndex).value > heap.get(largestIndex).value) {
                largestIndex = rightChildIndex;
            }
            
            if (largestIndex != currentIndex) {
                swap(currentIndex, largestIndex);
                currentIndex = largestIndex;
            } else {
                break;
            }
        }
    }
    
     public void printHeap() {
        for (Node node : heap) {
            System.out.println("Value: " + node.value + ", Index: " + node.index);
        }
    }
}

정리

• 예전에 동일한 문제를 최대힙으로 풀었던 기억이 있어서 최대힙으로 풀어보려고 했는데, 구현 불가 이슈로 예전에 js로 만들었던 max heap java로 옮겨달라 해서 풀었다
• 문제 잘못 읽어서 빙 돌아감
• heapifyDown 다시 봐도 이해가 잘 안간다.
• 확실히 자료구조를 사용하는 쪽이 사용처에서 코드가 더 깔끔하고 직관적 인 거 같다.
• java로 sort 내림차순하려니까 stream이 나오느데, 잘 몰라서 for문으로 바꿨다.
• 1번의 경우, 절차지향이라 읽기가 어려운 거 같다.