[medium] 406. Queue Reconstruction by Height

문제

https://leetcode.com/problems/queue-reconstruction-by-height/description/

Queue Reconstruction by Height - LeetCode

 

---

풀이방법

개인적으로 별로 안 좋아하는 문제 유형이다.
처음에 정렬하고 시작해서 그 다음은 조건 맞춰 구현만 하면 되는 문제
정렬방법은 사람마다 다른듯한데 나는 k를 우선순위로 하고 그 다음을 h로 해서 오름차순 정렬을 해서 구현이 좀 복잡해졌는데,
간단하게 하려면 h를 내림차순, k를 오름차순으로 하면 제일 간단해보인다
참고: https://leetcode.com/problems/queue-reconstruction-by-height/discuss/167308/Python-solution
시간복잡도 O(N^2), 공간복잡도 O(N)

반응형

---

코드

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        new_people = []
        people.sort(key=lambda x:(x[1],x[0]))
        
        for i, (h,k) in enumerate(people):
            if i == 0:
                new_people.append([h,k])
            else:
                cnt = 0
                flag = False
                
                for j, (hh,kk) in enumerate(new_people):
                    if cnt == k:
                        if kk != k:
                            new_people.insert(j,[h,k])
                            flag = True
                            break
                        elif kk == k and hh <= h:
                            continue
                    if hh >= h:
                        cnt += 1
                        
                if flag == False:
                    new_people.append([h,k])
        return new_people