[알고리즘] 명예의 전당 (1)

1. 조건

명예의 전당에 오를 수 있는 점수들은 총 k개 이다.

매일 새로운 가수가 한곡을 부르며, score가 갱신된다.

 

score가 갱신되면서 명예의전당에 등재된 최소 점수보다 높으면

최소 점수가 밀려나고 해당 score가 등재된다.

 

이때 매일 score가 갱신될때마다 최하위 점수들을 기록하여 배열로 return 하는게 최종 목표.

 

 

2. 풀이 과정

k의 범위는 3 <= k <= 1,000이고

score는 7 <= score <= 1,000이다.

 

k가 3이고 score도 최대 1000라고 생각하면

최대 997번 배열을 정렬하고 슬라이싱 및 answer 배열에 push 하는것이기 때문에

크게 시간초과는 나지 않을것 같았다.

 

 

3. 풀이

function solution(k, score) {
  const answer = [];
  let winners = [];

  for (let day = 0; day < score.length; day += 1) {
    winners.push(score[day]);
    winners.sort((a, b) => a - b);

    if (day > k - 1) winners = winners.slice(-k);

    answer.push(winners[0]);
  }

  return answer;
}