406 Queue Reconstruction by Height

• 406 Queue Reconstruction by Height
  • 문제
  • 조건
  • 예제
  • 해결
    • 1st
      • 1 생각
      • 1 코드
      • 1 결과: 실패(Wrong Answer)
    • 2nd
      • 2 생각
      • 2 코드
      • 2 결과: 성공

406 Queue Reconstruction by Height

문제

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).

• people: 사람들의 키 정보를 담고 있는 배열
• people[i] = [hi, ki]:
  • hi: i번째 사람의 키
  • ki: hi보다 크거나 같은 키를 가진 사람의 수
• 입력 배열 people가 나타내는 큐를 재구성하여 반환

조건

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

예제

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.

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]]

해결

1st

1 생각

• 풀이 참조
  • 모두 h가 같고, k가 다르다면? k를 인덱스로 배열을 생성하면 된다
    • [[7,1], [7,2], [7,0]] → [[7,0], [7,1], [7,2]]
    • 모두 키가 같지 않은 경우에도 이 전략은 적용된다.
      • 작은 사람은 큰 사람에게 보이지 않으므로(invisible), 키 큰 사람 먼저 정렬을 하면 된다
      • [[7,1], [7,2], [7,0], [6,1]]
      • [[7,0]]
      • [[7,0], [7,1]]
      • [[7,0], [7,1], [7,2]]
      • [[7,0], [6,1], [7,1], [7,2]]: [6,1]이 가장 마지막에 들어간다

1 코드

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
    people.sort(key=lambda person: person[0], reverse = True)
    
    result = []
    for person in people:
        result.insert(person[1], person)
    return result

1 결과: 실패(Wrong Answer)

Input:      [[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]

Output:     [[3,0],[6,0],[7,0],[5,2],[3,4],[6,2],[5,3],[2,7],[9,0],[1,9]]
Expected:   [[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]

[[9, 0], [7, 0], [6, 0], [6, 2], [5, 3], [5, 2], [3, 0], [3, 4], [2, 7], [1, 9]]
[[9, 0]]
[[7, 0], [9, 0]]
[[6, 0], [7, 0], [9, 0]]
[[6, 0], [7, 0], [6, 2], [9, 0]]
[[6, 0], [7, 0], [6, 2], [5, 3], [9, 0]] # 여기까진 맞다
[[6, 0], [7, 0], [5, 2], [6, 2], [5, 3], [9, 0]] # 하지만 [5, 2]가 들어 오면서 틀리게 된다
[[3, 0], [6, 0], [7, 0], [5, 2], [6, 2], [5, 3], [9, 0]]
[[3, 0], [6, 0], [7, 0], [5, 2], [3, 4], [6, 2], [5, 3], [9, 0]]
[[3, 0], [6, 0], [7, 0], [5, 2], [3, 4], [6, 2], [5, 3], [2, 7], [9, 0]]
[[3, 0], [6, 0], [7, 0], [5, 2], [3, 4], [6, 2], [5, 3], [2, 7], [9, 0], [1, 9]]


[[9, 0], [7, 0], [6, 0], [6, 2], [5, 2], [5, 3], [3, 0], [3, 4], [2, 7], [1, 9]]
[[9, 0]]
[[7, 0], [9, 0]]
[[6, 0], [7, 0], [9, 0]]
[[6, 0], [7, 0], [6, 2], [9, 0]]
[[6, 0], [7, 0], [5, 2], [6, 2], [9, 0]] # [5, 2]가 먼저 들어와야 한다. 같은 키면 더 큰 인덱스가 뒤로 가야 하기 때문
[[6, 0], [7, 0], [5, 2], [5, 3], [6, 2], [9, 0]]    
[[3, 0], [6, 0], [7, 0], [5, 2], [5, 3], [6, 2], [9, 0]]
[[3, 0], [6, 0], [7, 0], [5, 2], [3, 4], [5, 3], [6, 2], [9, 0]]
[[3, 0], [6, 0], [7, 0], [5, 2], [3, 4], [5, 3], [6, 2], [2, 7], [9, 0]]
[[3, 0], [6, 0], [7, 0], [5, 2], [3, 4], [5, 3], [6, 2], [2, 7], [9, 0], [1, 9]]

• [6,2],[5,3]이 바뀌어야 한다

2nd

2 생각

• 큰 키 순서대로 정렬(내림차순)
• 같은 키인 경우 인덱스 순으로 정렬(오름차순)

2 코드

def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
    people.sort(key=lambda person: (-person[0], person[1]))
    result = []
    for person in people:
        result.insert(person[1], person)
    return result

2 결과: 성공

Runtime: 92 ms, faster than 86.52% of Python3 online submissions for Queue Reconstruction by Height.
Memory Usage: 14.9 MB, less than 59.71% of Python3 online submissions for Queue Reconstruction by Height.