[그리디] Leet code 406. Queue Reconstruction by Height

리트코드 406번
사람의 키와 자기보다 같거나 큰 사람의 수가 차례로 주어질 때 모두 만족하는 줄세우기

풀이1. stack + deque + 정렬

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key= lambda x : (-x[0],x[1])) # 키에 대해서는 내림차순 앞에 있는 사람수에 대해서는 내림차순 
        result = collections.deque()
        stack = []

        for person in people:
            count = person[1]
            
            # 앞에서 부터 pop
            while count !=0 and len(result) != 0:
                stack.append(result.popleft())
                count -= 1
            
            # 적당한 자리에 넣어주기 
            result.appendleft(person)
            
            # 앞에 pop한거 다시넣어주기 
            while len(stack) != 0:
                result.appendleft(stack.pop())


        return result

• 자신의 키이상인 사람이 앞에 몇명이나 있는지 매번 계산해주는 것은 매우 비효율..
  -> 항상 자신보다 크거나 같도록 하자 : 내림차순 정렬을 해서 제일 큰 사람부터 넣으면 항상 자신보다 키가 이상이다

• 만약 같은 키이면 뒤에 수가 더 작은 사람이 먼저 들어가야한다 그래야지 나중에도 앞에오는 키가 큰 사람의 수가 보장이 된다

• ⭐️그리디 알고리즘의 핵심⭐️ : 매번 가장 최적의 해를 찾는다! 그리고 그해가 다음 번에 영향을 받으면 안된다

• 지금 같은 경우 (5,1)을 (5,0)보다 먼저 넣어준다면 나중에 (5,0)이 (5,1)보다 앞에 오면서 (5,1)일 때 앞에 1개를 뒀다면 앞에 2개가 되어버린다... 상황이 달라진것 따라서 순서를 (5,0) (5,1)순으로 넣어주면 그럴 일이 없다

풀이2. insert함수를 이용한 최적화

왜 지금 알았을 까.. ㅎㅎ python에 리스트의 내장함수중 insert를 이용하면 원하는 인덱스에 넣어줄 수 있다. 나머지는 뒤로 알아서 밀린다
엄청난 속도 차이다 10배정도 차이가 난다...

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

• 주의해야할 점은 insert()는 만약 그 해당 index가 없다면 error가 나는게 아니라 그냥 무시하고 그 다음으로 넣을 수 있는 곳에 넣는다. 예를 들어 빈 리스트에 insert(4,1)을 한다면 그냥 [1]이 된다
• 여기서는 정답이 있기 때문에 정렬을 잘 해줘서 항상 해당 index가 있도록 만들었다.