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

 

 

오늘의 문제는 Leetcode

 

 

Relative Ranks 

 

 

문제

 

 

 

 

문제 접근 및 풀이 과정

권장 풀이 시간은 30분이었고, 저는 30분이 걸렸습니다.

 

 

 

 

문제 접근 방식

먼저 최대 힙을 통해 가장 높은 점수의 인덱스가 먼저 나오도록 정렬합니다. 그 다음 반복문을 통해 score의 인덱스를 최대 힙에 추가합니다. 마지막으로 조건문에서 각 순위를 인덱스를 사용해 결과를 출력할 배열 answer에 저장합니다.

 

 

문제 풀이

import java.util.PriorityQueue;
class Solution {
    public String[] findRelativeRanks(int[] score) {

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> score[b] - score[a]);

    int n = score.length; 

    String[] strArr = new String[n]; 

    for(int i = 0; i < n; i++) {
        int num = score[i];
        maxHeap.add(i); 
    }

    int num = 1; 
    while(!maxHeap.isEmpty()) {
        int index = maxHeap.poll();
        if(num == 1) {
            strArr[index] = "Gold Medal";
        } else if(num == 2) {
            strArr[index] = "Silver Medal";
        } else if(num == 3) {
            strArr[index] = "Bronze Medal";
        } else {
            strArr[index] = String.valueOf(num);
        }
        num++; 
    }

    return strArr; 
    }
}

 

 

우선순위 큐 사용하기 

우선순위 큐를 사용해 점수가 높은 순으로 정렬합니다. 

점수를 비교해 높은 점수를 가진 인덱스를 큐에서 먼저 꺼낼 수 있도록 비교자를 사용하여 점수 배열에서 score[a]와 score[b]의 값을 비교합니다. 

 

 

반복문을 통한 인덱스 추가하기 

i는 점수 배열 score의 인덱스를 의미하며 maxHeap에 추가됩니다. 이 때 maxHeap은 비교자를 사용해 점수 배열의 점수에 따라 인덱스를 정렬합니다. 

 

 

 

반복문을 통해 순위 부여하기 

while문을 통한 순위 부여 방법입니다. 현재 순위를 나타내는 변수를 1로 초기화합니다. while문은 maxHeap이 비어있지 않을 때까지 반복합니다. poll() 메서드를 사용해 큐에서 가장 높은 우선순위를 반환 및 제거합니다. 반환된 인덱스를 결과를 저장할 배열  answer에 저장합니다. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이렇게 오늘 9일차 TIL을 작성해 보았습니다.