[JavaScript] 명예의 전당 - 프로그래머스

문제 :

 

내 풀이 :

function solution(k, scores) {
    let answer = [];
    let hallOfFame = [];
    
    for (let i = 0; i < scores.length; i++) {
        hallOfFame.push(scores[i]);
        hallOfFame.sort((a, b) => b - a);
        if (hallOfFame.length > k) {
            hallOfFame.pop();
        }
        answer.push(hallOfFame[hallOfFame.length - 1]);
    }
    
    return answer;
}

 

 

1. answer는 최종적으로 반환할 배열이다. 이 배열에는 각 회차에서 상위 k명 중 가장 낮은 점수가 들어간다.

 

2. hallOfFame은 현재까지 누적된 점수 중 상위 k개를 저장할 배열이다.

 

3. 각 회차에서 점수를 하나씩 hallOfFame에 추가한 후, 이 배열을 내림차순으로 정렬한다. 가장 큰 값부터 정렬되므로 상위 k개의 점수는 배열의 앞부분에 있게 된다.

 

4. 만약 hallOfFame의 길이가 k보다 크면( 상위 k개 이상의 점수가 들어오면 ) pop()을 사용해 가장 작은 점수를 제거하여 hallOfFame은 항상 최대 k개의 값만 유지하게 된다.

 

5. 상위 k개의 점수가 유지된 hallOfFame 배열에서 가장 마지막 값( hallOfFame[hallOfFame.length - 1] )은 현재 상위 k개의 점수 중 가장 작은 값이고 이 값을 answer 배열에 추가한다.

 

6. 이 과정이 반복되면서 매 회차마다 상위 k명의 점수 중 가장 작은 값이 answer에 추가된다.

 

예시)

k = 4 이고, scores = [0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]

 

i = 0, scores[ i ] = 0:

• hallOfFame = [0] (0을 추가)
• answer = [0] (명예의 전당에 1명밖에 없으므로 가장 낮은 값은 0)

i = 1, scores[ i ] = 300:

• hallOfFame = [300, 0] (300을 추가 후 정렬)
• answer = [0, 0] (가장 낮은 값은 0)

i = 2, scores[ i ] = 40:

• hallOfFame = [300, 40, 0] (40을 추가 후 정렬)
• answer = [0, 0, 0] (가장 낮은 값은 0)

i = 3, scores[ i ] = 300:

• hallOfFame = [300, 300, 40, 0] (300을 추가 후 정렬)
• answer = [0, 0, 0, 0] (가장 낮은 값은 0)

i = 4, scores[ i ] = 20:

• hallOfFame = [300, 300, 40, 20, 0] → 5개가 되므로 가장 작은 값 0을 제거 → hallOfFame = [300, 300, 40, 20]
• answer = [0, 0, 0, 0, 20] (가장 낮은 값은 20)

i = 5, scores[ i ] = 70:

• hallOfFame = [300, 300, 70, 40, 20] → 가장 작은 값 20을 제거 → hallOfFame = [300, 300, 70, 40]
• answer = [0, 0, 0, 0, 20, 40] (가장 낮은 값은 40)

i = 6, scores[ i ] = 150:

• hallOfFame = [300, 300, 150, 70, 40] → 가장 작은 값 40을 제거 → hallOfFame = [300, 300, 150, 70]
• answer = [0, 0, 0, 0, 20, 40, 70] (가장 낮은 값은 70)

i = 7, scores[ i ] = 50:

• hallOfFame = [300, 300, 150, 70, 50] → 가장 작은 값 50을 제거 → hallOfFame = [300, 300, 150, 70]
• answer = [0, 0, 0, 0, 20, 40, 70, 70] (가장 낮은 값은 70)

i = 8, scores[ i ] = 500:

• hallOfFame = [500, 300, 300, 150, 70] → 가장 작은 값 70을 제거 → hallOfFame = [500, 300, 300, 150]
• answer = [0, 0, 0, 0, 20, 40, 70, 70, 150] (가장 낮은 값은 150)

i = 9, scores[ i ] = 1000:

• hallOfFame = [1000, 500, 300, 300, 150] → 가장 작은 값 150을 제거 → hallOfFame = [1000, 500, 300, 300]
• answer = [0, 0, 0, 0, 20, 40, 70, 70, 150, 300] (가장 낮은 값은 300)

최종 결과는 answer = [0, 0, 0, 0, 20, 40, 70, 70, 150, 300] 이다.