Team formation / 코딩테스트 문제

난이도 : Medium

특징 : Priority Queue

 

---

요구사항

 

입출력 예시

 

Hackerrank invitation으로 온 문제라서.. 문제에대한 링크를 걸 수가 없다. 

Sample Input 1

1. 첫 번째 줄에는 배열의 크기 값

2. 두 번째 줄 이후는 배열의 각 요소이다.

3. 마지막에서 2번째 줄은 만들어야하는 팀원의 수

4. 마지막 줄은 Manager가 팀원을 뽑기 위해서 배열에서 선택하는 그룹의 크기를 의미한다.

 

대략적인 흐름

 

단순히 구현으로만 생각하면 생성하는 그룹마다, python의 max 내장 함수로 처리하면 되겠지만 어느정도 입력이 커지면 Timeout이 나버린다. 

개인적으로 2가지 성능에 큰 영향을 미치는 부분은

1. Manager가 선택한 그룹에서 최댓값을 찾는 코드

2. 선택한 두 가지 그룹에서 최댓값이 오른쪽 그룹에 있을때, 이를 원래 배열에서 삭제하는 코드

라고 생각한다.

 

Hackerrank 테스트를 해볼 수가 없어서 확인은 못했지만, 각 그룹에서 max를 구하는 부분을 max heap 구조를 구현해서 첫 번째 인덱스를 리턴하는 방식으로 풀면 좋을 것 같다.

 

heapify 코드 / 출처 :https://smlee729.github.io/python/data%20structure/2015/03/04/1-heap.html

class Heap:

    def __init__(self, arr):
        self.queue = [None]
        self.queue.extend(arr)
        for i in range(int(len(self.queue)/2),0,-1):
            self.max_heapify(i)

    def max_heapify(self, i):
        largest = i
        left = i*2
        right = i*2+1
        
        if left <= len(self.queue)-1 and self.queue[largest] < self.queue[left]:
            largest = left
        if right <= len(self.queue)-1 and self.queue[largest] < self.queue[right]:
            largest = right
        if largest != i:
            self.queue[i], self.queue[largest] = self.queue[largest], self.queue[i]
            self.max_heapify(largest)

    def print_all(self):
        print('After heapify : {0} / 최댓값 : {1}'.format(self.queue, self.queue[1]))
        
def main():
    tmp = [6, 18, 8]
    print('Manager가 선택한 그룹1 : {0}'.format(tmp))
    tmp = Heap(tmp)
    tmp.print_all()
    
    tmp = [12, 18, 9]
    print('Manager가 선택한 그룹2 : {0}'.format(tmp))

    tmp = Heap(tmp)
    tmp.print_all()

 

결과

Manager가 선택한 그룹1 : [6, 18, 8]
After heapify : [None, 18, 6, 8] / 최댓값 : 18
Manager가 선택한 그룹2 : [12, 18, 9]
After heapify : [None, 18, 12, 9] / 최댓값 : 18
>>>