LeetCode - Queue Reconstruction by Height (Javascript)

문제 설명

You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.

Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).

Example 1:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.

Example 2:

Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

Constraints:

• 1 <= people.length <= 2000
• 0 <= hi <= 106
• 0 <= ki < people.length
• It is guaranteed that the queue can be reconstructed.

---

소스 코드

splice를 활용해서 문제를 풀었다.
우선, 키가 큰 사람들의 위치를 먼저 배치해야 작은 사람들의 위치가 적절히 결정될 수 있기에, 키순 오름차순 정렬을 제일 먼저 수행했다.

const reconstructQueue = (people) => {
  const answer = [];
  people.sort((a, b) => {
    if (a[0] === b[0]) return a[1] - b[1];
    else return b[0] - a[0];
  });
  for (let person of people) answer.splice(person[1], 0, person);
  return answer;
};

---

풀이 과정

splice의 특성을 잘 파악하면 굉장히 쉽게 해결할 수 있는 문제다.

먼저, 아래와 같이 키 내림차순으로 정렬해준다. (만약 키가 같을 경우에는 k 기준 오름차순으로 정렬)

그리고 반복문을 통해 각 요소들을 result 배열의 k번째 자리에 추가해준다. 이를 splice를 통해 구현해야 한다. 먼저, 빈 answer 배열에 answer.splice(person[1], 0, person)을 통해 아래와 같이 0번째 index에 person을 추가해준다.

그리고 또 다시 [5,0]을 answer의 0번째 index에 추가해줘야 하기 때문에 기존의 [6,0]은 index 1로 밀린다. 따라서 answer의 배열 형태는 아래와 같이 될 것이다.

그리고 반복문을 이어가다 보면, 아래 그림처럼 0번째 인덱스에 대한 정리는 마무리 된다.

그리고 이 아래의 경우부터 splice를 사용한 목적이 드러난다.

[3,2]라는 사람은 자신보다 키가 큰 사람이 앞에 두 명 있어야 한다. 따라서 index 2에 배치해주면 자연스럽게 자신의 앞에는 자신보다 큰 키를 가진 사람이 두 명 존재하게 되며 조건을 만족한다.

그리고 그 다음의 경우에도 [2,2]는 [3,2]를 밀어내고 2번 인덱스를 차지한다.

이런식으로 키가 큰 사람들을 우선적으로 알맞은 인덱스에 배치한 후에, 작은 사람들이 정확한 위치에 배치될 수 있도록 splice를 사용한 것이다.

---