99클럽 코테 스터디 9일차 TIL (Heap - Relative Ranks)

문제 설명

정수 배열 score가 주어졌습니다. 이 배열의 크기는 n이며, score[i]는 대회에서 i번째 운동선수의 점수를 나타냅니다. 모든 점수는 고유함이 보장됩니다.

운동선수들은 점수를 기준으로 순위가 매겨지며, 1등은 가장 높은 점수를, 2등은 두 번째로 높은 점수를, 그 다음은 순서대로 점수를 기준으로 순위가 매겨집니다. 각 운동선수의 순위는 다음과 같이 결정됩니다

1. 1등 운동선수의 순위는 "Gold Medal"(금메달)입니다.
2. 2등 운동선수의 순위는 "Silver Medal"(은메달)입니다.
3. 3등 운동선수의 순위는 "Bronze Medal"(동메달)입니다.
4. 4등부터 n등까지의 운동선수의 순위는 그들의 등수 숫자입니다 (예: 4등 운동선수의 순위는 "4"입니다).

이제 각 운동선수의 순위를 담은 배열 answer를 반환하세요. answer[i]는 i번째 운동선수의 순위입니다.

제한 조건

• n == score.length
• 1 <= n <= 104
• 0 <= score[i] <= 106
• 점수는 모두 고유합니다.

입출력 예

• 입력: score = [5, 4, 3, 2, 1]
• 출력: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
• 설명: 순위는 [1등, 2등, 3등, 4등, 5등]입니다.

• 입력: score = [10, 3, 8, 9, 4]
• 출력: ["Gold Medal", "5", "Bronze Medal", "Silver Medal", "4"]
• 설명: 순위는 [1등, 5등, 3등, 2등, 4등]입니다.

---

나의 풀이

public static String[] solution9(int[] score) {
    int size = score.length;

    int[][] sortedScore = new int[size][2];
    for (int i = 0; i < size; i++) {
        sortedScore[i] = new int[] {score[i],i};
    }
    
    Arrays.sort(sortedScore, (a,b) -> (b[0]-a[0]));

    String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
    String[] result = new String[size];

    for (int i = 0; i < sortedScore.length; i++) {
        if(i <= 2){
            result[sortedScore[i][1]] = medals[i];
        }else{
            result[sortedScore[i][1]] = String.valueOf(i + 1);
        }
    }

    return result;
}

2차원 배열을 초기화 한 후 인덱스도 같이 추가를 해줬다.
// [10,0], [3,1], [8,2], [9.3], [4,4]


이후, [n][0]을 기준으로 내림차순 정렬을 하게 되면
// [10,0], [9,3], [8,2], [4,4], [3,1]

for문 안 i <= 2 조건에 result[sortedScore[i][1]] 에서는 0, 3, 2가 순서대로 반환되고
result[0] = "Gold Medal"
result[3] = "Silver Medal"
result[2] = "Bronze Medal"

나머지 else 에서는
result[4] = i + 1 = 3 + 1
result[1] = i + 1 = 4 + 1

---

Heap이란

완전 이진트리의 일종(Complete Binary Tree)

* 완전 이진트리
: 부모 노드 밑에 자식 노드는 최대 2개까지, 마지막 레벨을 제외한 모든 레벨에 노드가 완전 채워진 트리구조
힙에서는 부모 노드, 자식 노드, 루트, 리프, 레벨, 높이 용어 사용

부모 노드 : 특정 노드의 상위에 위치
자식 노드 : 특정 노드의 하위에 위치
루트 노드 : 트리 구조에서 가장 상위
리프 노드 : 트리 구조에서 가장 하위하면서 자식 노드가 없는 노드
레벨 : 루트 노드를 시작으로 트리의 몇 번째 층 (루트 노드는 레벨0)
높이 : 리프 노드를 시작으로 한다. (루프 노드 높이 == 트리 전체 높이)

힙의 종류
최대힙 : 모든 부모 노드가 자식 노드보다 크거나 같다. 이러한 특성때문에 루트노드가 가장 큰 값을 가진다
한 노드를 기준으로 자식 노드 왼쪽은 2*i, 오른쪽은 2*i+1 이다

최소힙 : 모든 부모 노드가 자식 노드보다 작거나 같다. 루트노드가 가장 작은 값을 가진다

https://yozm.wishket.com/magazine/detail/2312/

자료구조 개념 이해하기 ‘힙과 힙 정렬 알고리즘’ | 요즘IT

회고

• Heap 자료구조에 대해 정의, 종류, 노드위치에 관해 차근차근 메모장에 정리해가면서 스스로 이해시켰다
  옼케이! 이론 이해는 했어!! 하지만 이걸 코드로 구현할려니 막막 그 잡채...

public class MinHeap {

    public int[] heap;
    public int size;

    public void build_min_heap(int[] arr) {
        this.size = arr.length;
        this.heap = new int[size + 1];

        System.arraycopy(arr, 0, heap, 1, size);

        for (int i = size/2; i >= 1; i--) {
            min_heapify(i);
        }

    }

    public void min_heapify(int i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        int smallest;

        if (left <= size && heap[left] < heap[i]) {
            smallest = left;
        }else{
            smallest = i;
        }

        if (right <= size && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (smallest != i) {
            swap(i, smallest);
            min_heapify(smallest);
        }
    }

    public void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    void printHeapArray(){
        for (int i = 1; i <= size; i++) {
            System.out.println(heap[i] + " ");
        }
        System.out.println();
    }
}

• 위 기본 구현 예제대로 풀려다가 사고가 멈춰버렸다... 
  추가적으로 검색을 했고 그 결과가 나의 풀이 코드다. (기본 예제코드랑 생각보다 달라서 허무했다.)
  따라치면서 나의 풀이 코드를 이해했다. 
  저 방식이 힙(Heap) 자료구조를 사용한건지? 생각이 들었는데 최대 힙인것 같다.
  Queue랑 비슷한 것 같이 느껴진다..
  어려워ㅠㅠ