[파이썬 알고리즘 인터뷰][그리디] 키에 따른 대기열 재구성

 

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

(내 키, 앞에 줄 선 사람 중 내 키 이상인 사람)이 주어질 때 재정렬

 

책에서 구현된 코드

import heapq
from typing import List


class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        heap = []
        # 키 역순, 인덱스 삽입
        for person in people:
            heapq.heappush(heap, (-person[0], person[1]))

        result = []
        # 키 역순, 인덱스 추출
        while heap:
            person = heapq.heappop(heap)
            result.insert(person[1], [-person[0], person[1]])
        return result

 

기억해야할 기법

• 그리디 알고리즘에 접근을 못하는 것 같다
  
  • 문제 풀이만 보면 간단명료한데, 이렇게 풀어야 한다는 도출을 못했다
  • 나보다 큰 사람을 알고 있으니, 큰 사람부터 처리하면 인덱스가 간단하게 도출된다
• 그리디 알고리즘에는 우선순위 큐를 먼저 고려해보자

 

내가 구현한 코드

from typing import List

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        answer = [[] for _ in range(len(people))]
        idx = [i for i in range(len(people))]
        prev = (-1, 0)
        for v, i in sorted(people):
            crnt_i = i
            if prev[0] != v:
                prev = (v, 1)
            else:
                crnt_i, prev = crnt_i - prev[1], (prev[0], prev[1] + 1)
            answer[idx[crnt_i]].append(v)
            answer[idx[crnt_i]].append(i)
            del idx[crnt_i]
        return answer

• 틀리진 않지만 문제 접근이 이상하다 ㅠㅠ
  • 키가 작은 사람부터 처리했다
  • 이전 키와 인덱스를 매 루프 계산해야됐다