LeetCode 406 - Queue Reconstruction by Height (Medium)

문제

LeetCode - 406번

풀이 과정

각 사람들의 키 h 와 자신보다 앞에 서있는 사람들 중 자신보다 키가 큰 사람들의 수 n 이 주어질 때
조건에 맞도록 사람들을 나열하는 방법을 찾는 문제입니다.

따라서 우선 n 의 오름차순으로 정렬하며 n 이 같을 경우에는 h 가 증가하는 순으로 정렬합니다.

그리고 정렬된 사람들을 한명씩 자신의 위치를 찾아 삽입해주는 방식으로 진행합니다.
이때 n 을 만족시키면서 최대한 뒤에 위치하도록 설정해주도록 하는 탐욕적 선택 을 활용합니다.

코드

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
var reconstructQueue = function (people) {
  const answer = [];

  people.sort((a, b) => a[1] - b[1] || a[0] - b[0]);

  people.forEach((p) => {
    let count = 0,
      i = 0;
    for (; i < answer.length; i++) {
      if (answer[i][0] >= p[0]) count++;
      if (count > p[1]) break;
    }

    answer.splice(i, 0, p);
  });

  return answer;
};