[코딩테스트] Queue 큐 _코딩테스트 (key, sorted) 키별로 사람 줄 세우기 문제 | List 정렬할 때 Key값 설정 & index함수

| Array에서 정렬하는 파라미터 Key

#sorted에 아무런 key값 주지 않을 경우, 기본 ascending으로 출력
array = [3, 1, 5, 2, 4]
sorted_array = sorted(array)
print(sorted_array)  # 출력: [1, 2, 3, 4, 5]

#key=lambda x: x[0]
#튜플에서 각 첫번째 요소 기준으로, 오름차순 정렬
array = [(1, 'b'), (3, 'a'), (2, 'c')]
sorted_array = sorted(array, key=lambda x: x[0])
print(sorted_array)  # 출력: [(1, 'b'), (2, 'c'), (3, 'a')]

#key=len
#문자열의 길이에 따른 정렬
array = ['apple', 'banana', 'orange', 'kiwi']
sorted_array = sorted(array, key=len)
print(sorted_array)  # 출력: ['kiwi', 'apple', 'banana', 'orange']


#key=lambda x: x[0], -x[1]
#첫번째 요소 기준으로 내림차순, 두번째 요소 기준으로 오름차순 정렬할 때
array = [(3, 'b'), (1, 'c'), (2, 'a'), (1, 'a'), (2, 'b')]
sorted_array = sorted(array, key=lambda x: (-x[0], x[1]))
print(sorted_array)
#출력 : [(3, 'b'), (2, 'a'), (2, 'b'), (1, 'a'), (1, 'c')
#첫번째 요소 기준으로 먼저 쭉 내림차순 되고, 그 다음 그 안에서 오름차순이 이뤄진다

다만, 여기서 key=lambda x : (x[1], -x[0]))
이렇게 순서를 바꿔쓰면, 두번째 요소 기준 정렬이 더 우선적으로 적용되어
a, b, c 순서가 먼저 지켜지고 그 다음에 그 안에서, 첫번째 요소의 내림차순이 이뤄진다
# 출력: [(2, 'a'), (1, 'a'), (3, 'b'), (2, 'b'), (1, 'c')]

 

 

| Insert

#insert는 넣을 위치 & 넣을 값을 써준다
list.insert(index, element)


#예시
my_list = [1, 2, 3, 4, 5]
my_list.insert(2, 10)
print(my_list)  # 출력: [1, 2, 10, 3, 4, 5]

#[2] 인덱스 위치에 10을 넣었고, 나머지는 한칸씩 뒤로 밀린다

 

 

이걸 알아야, 다음 문제를 풀 수 있다

 

 

문제

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


Example 1:

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

 

풀이

1. 사람들을 키에 따라 내림차순, 앞에있는 사람 수에 따라 오름차순을 한다

ex) people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

      people_sorted = sorted(people, key = lambda x: (-x[0],x[1]))

      people_sorted = [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

                                       0        1        2       3        4        5 

 

2 각각의 사람들은 [키, 앞에 자기보다 키가 크거나 같은 사람 수] = [i, j]

people_sorted 내의 자기의 인덱스는, 이제 j보다 크거나 같을거다. 당연히 그럴수밖에 없다. 

j의 최대값은 len(people_sorted) -1 니까 결국 최대 인덱스보다 작거나 같은거다!! 

 

3.  빈 리스트 하나 생성해서, 왼쪽에서부터 poeple_sorted의 [i,j] 를  j 위치에 넣어주도록 한다. 

나중에 갈수록 키가 작은 사람들이 추가될 것이고, 그건 큰 사람들의 j값에 영향을 미치지 않는다

 

[[7,0]] (insert [7,0] at index 0)
[[7,0],[7,1]] (insert [7,1] at index 1)
[[7,0],[6,1],[7,1]] (insert [6,1] at index 1)
[[5,0],[7,0],[6,1],[7,1]] (insert [5,0] at index 0)
[[5,0],[7,0],[5,2],[6,1],[7,1]] (insert [5,2] at index 2)
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] (insert [4,4] at index 4)

 

4. 소요 시간은 O(n^2)이고, 공간복잡도는 O(n)이다

 

 

정답

class Solution:
    def reconstructQueue(self, people):
        people = sorted(people, key = lambda x: (-x[0], x[1]))
        res = []
        for i in people:
            res.insert(i[1],i)
        return res