[정렬삽입 or 세그먼트 트리] 406. Queue Reconstruction by Height ★★★

406. Queue Reconstruction by Height

 

LeetCode 406번 문제 "Queue Reconstruction by Height" 는 사람들의 [키, 앞에 있어야 할 사람 수] 조건을 바탕으로 원래의 줄(큐) 을 복원하는 문제예요.

---

✅ 문제 요약

각 사람 people[i] = [hi, ki]는 다음을 의미해요:

• hi: 이 사람의 키
• ki: 이 사람보다 키가 크거나 같은 사람이 앞에 정확히 ki명 있어야 한다

---

 

✅ 핵심 아이디어 (그리디 + 정렬 + 삽입)

1. 키가 큰 사람부터 정렬 (내림차순)
   • 이유: 키가 큰 사람이 먼저 자리를 차지해야 작은 사람이 영향을 안 받음
2. 같은 키일 경우 ki 오름차순 정렬
   • 이유: 같은 키라면, ki가 작을수록 먼저 위치해야 조건이 맞음
3. 정렬된 순서대로 ki 위치에 삽입
   • 삽입 시점에는 자신보다 키가 크거나 같은 사람만 앞에 있으므로 ki만큼 앞에 있는 사람이 맞음

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

정렬 결과:
[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

삽입 과정:
[7,0] → [ [7,0] ]
[7,1] → [ [7,0], [7,1] ]
[6,1] → [ [7,0], [6,1], [7,1] ]
[5,0] → [ [5,0], [7,0], [6,1], [7,1] ]
[5,2] → [ [5,0], [7,0], [5,2], [6,1], [7,1] ]
[4,4] → [ [5,0], [7,0], [5,2], [6,1], [4,4], [7,1] ]

최종 결과:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

 

✅ 코드 (주석 포함)

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        # 1. 키(h) 내림차순, 같은 키는 k 오름차순 정렬
        people.sort(key=lambda x: (-x[0], x[1]))
        
        queue = []  # 최종 결과를 담을 리스트

        # 2. 각 사람을 자신의 k 위치에 삽입
        for person in people:
            h, k = person
            queue.insert(k, person)  # k번째 위치에 삽입
            # 삽입하면 자동으로 k명 만큼 키 큰 사람이 앞에 있게 됨

        return queue

 

✅ 시간복잡도

• 정렬: O(n log n)
• 삽입: O(n²) (리스트 중간 삽입)

---

 

이제 LeetCode 406번 문제를 세그먼트 트리를 사용해서 푸는 고급 버전으로 설명
이 방법은 시간복잡도를 줄이고 리스트 중간 삽입의 단점을 해결하기 위한 방법이에요.

---

✅ 핵심 아이디어 (세그먼트 트리)

문제에서 중요한 포인트:

• 각 사람 [h, k]는 "자기보다 키가 크거나 같은 사람"이 **정확히 k명 앞에 있어야 한다.
• 큰 키 사람부터 먼저 자리를 잡아야, 작은 키 사람을 배치할 때 영향이 없음.

---

🔍 전략 요약

1. 사람들을 키 오름차순, k 내림차순으로 정렬함 (작은 키부터 놓기 위해).
2. 전체 자리를 n개로 보고, 처음엔 모두 빈 자리로 생각.
3. 세그먼트 트리를 통해 k번째 빈 자리의 위치를 빠르게 찾아서, 해당 위치에 사람을 놓음.
4. 빈 자리를 사용하면 트리에서 그 자리는 unavailable 처리.

---

✅ 세그먼트 트리 구조

• 각 노드는 그 구간에 비어 있는 자리 수를 나타냄.
• 예: 노드가 [0, 3] 범위를 담당하고, 현재 이 안에 빈 자리가 3개라면 tree[node] = 3

---

✅ 파이썬 구현 (전체 코드 + 상세 주석)

class SegmentTree:
    def __init__(self, size):
        self.N = size
        self.tree = [0] * (4 * size)
        self.build(0, 0, size - 1)

    def build(self, node, l, r):
        if l == r:
            self.tree[node] = 1  # 처음엔 모든 자리가 비어 있음
        else:
            mid = (l + r) // 2
            self.build(2 * node + 1, l, mid)
            self.build(2 * node + 2, mid + 1, r)
            self.tree[node] = self.tree[2 * node + 1] + self.tree[2 * node + 2]

    # k번째 빈 자리를 찾아서 그 자리에 사람을 넣고, 그 자리는 더 이상 못 쓰게 처리
    def insert(self, node, l, r, k):
        self.tree[node] -= 1  # 자리를 하나 차지함
        if l == r:
            return l  # 찾은 자리의 인덱스 반환
        mid = (l + r) // 2
        if self.tree[2 * node + 1] > k:
            return self.insert(2 * node + 1, l, mid, k)
        else:
            return self.insert(2 * node + 2, mid + 1, r, k - self.tree[2 * node + 1])

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        n = len(people)
        
        # 키 오름차순, k 내림차순 정렬
        people.sort(key=lambda x: (x[0], -x[1]))

        st = SegmentTree(n)           # n개의 자리 생성
        res = [None] * n              # 결과 리스트 (자리에 사람을 배치)

        for h, k in people:
            idx = st.insert(0, 0, n - 1, k)  # k번째 빈 자리 찾기
            res[idx] = [h, k]                # 해당 자리에 사람 배치

        return res

 

⏱️ 시간 복잡도

단계	복잡도
정렬	O(n log n)
각 삽입	O(log n)
전체 삽입	O(n log n)

➡️ 총 시간복잡도: O(n log n) (기존 삽입 방식의 O(n²)보다 훨씬 빠름)

---

✅ 요약

방법	특징	시간 복잡도
기본 정렬 + 리스트 삽입	쉬움, 느림	O(n²)
세그먼트 트리	어렵지만 빠름	O(n log n)