이전 문제인 최소 힙과 최대 힙하고 비슷한 문제이지만 이 문제에서는 절대값으로 저장을 한다 따라서 숫자를 받을때 음수와 양수를 어떻게 처리하는지가 중요하다

최소 힙 문제로 이전 문제 최대 힙과 같은 문제이다 최대 힙을 구현할때는 음수로 지정해서 힙에 넣었지만 이번에는 그냥 넣으면 최소 힙이 바로된다

이번 문제는 우선 순위 큐를 이용한 문제이다 우선순위 큐에서 최대 힙을 이용한다 파이썬에 내장된 함수 heapq를 이용해서 쉽게 풀 수 있었다

이 문제도 이분 탐색 문제로 최대값과 최소값을 잘 설정한뒤에 이분 탐색을 하면된다 python으로 제출할시에 시간초과가 나와서 pypy3로 제출했다

순차탐색을 이용해서 풀 수도 있지만 당연히 시간 초과가 나올것이다 이분탐색을 이용하여 시간을 단축시켜야한다 이분 탐색문제로 최대 랜선의 길이와 최소랜선의 길이(1)로 해결 가능하다

이분 탐색은 정렬된 숫자중에서 특정값을 찾는것인데 이문제에 어떻게 접목시켜야하는지 고민했다

중복이 있는 경우 이분 탐색을 어떻게 사용할것인가?

이진 탐색은 정렬이된 리스트나 배열에서 사용이 가능하다 그래서 먼저 리스트를 정렬하고 중간지점을 찾아 중간지점의 수와 탐색하는 숫자를 비교하고 크면 오른쪽범위의 절반을 찾아 다시 비교한다

이번 문제는 부분합을 이용하는것이지만 한개의 리스트로 이루어진 것이 아니라 이중리스트 2차원 배열을 이용한는것이다 따라서 부분합을 구할때 처음부터 차례대로 부분합을 구하는 방법을 사용하면 이문제를 해결하기 어렵다

문제를 해석해보면 부분합을 이용해서 문제를 해결해야한다 먼저 부분합을 구하고 구간의 합이 M으로 나누어 떨어져야한다