1. 문제
수열이 여러 개(N개) 있을 때, 각 수열에서 수를 하나씩만 고릅니다.
그렇게 고른 수 중 최대값과 최소값의 차이가 가장 작게 골라봅시다.
예를 들어, {49, 97, 1, 64, 25}, {93, 33, 54, 78, 12}, {71, 6, 80, 20, 44}가 있을 때, 각 수열에서 수 하나씩 고릅니다.
이 때 만약 첫 번째 수열에서 49, 두 번째 수열에서 54, 세 번째 수열에서 44를 고른다면, 이 중 최대값인 54와 최소값인 44의 차이는 10입니다.
이렇게 선택한 수 중 최대값과 최소값의 차이가 가장 작게 고르는 방법을 알아봅시다.
2. 해결 방법
가. Brute-force
모든 경우의 수를 일일이 살펴보고, 정답을 찾는 방법입니다.
구현하기 가장 쉽지만, 비효율적입니다.
시간복잡도를 계산해보면 수열의 개수를 N, 수열의 길이를 M이라고 할 때, \(O(M^{N})\)으로 N이 좀만 커져도 현실적으로 사용하기가 불가능합니다.
S = [
[49, 97, 1, 64, 25],
[93, 33, 54, 78, 12],
[71, 6, 80, 20, 44]
]
res = [float("inf"), []]
def recur(depth, mn, mx, arr):
if depth == len(S):
if res[0] > mx-mn:
res[0] = mx-mn
res[1] = arr
return
for i in range(len(S[depth])):
cur = S[depth][i]
recur(depth+1, min(mn, cur), max(mx, cur), arr+[cur])
recur(0, float("inf"), 0, [])
print(*res, sep="\n")
# 10
# [49, 54, 44]나. Sort + Greedy
각 수열에서 숫자를 고를 때, 최대한 비슷한 숫자들끼리 고르는 것이 유리하다는 것을 알 수 있습니다.
따라서 각 수열을 정렬하여 그리디하게 숫자를 고르면 더 효율적으로 고를 수 있습니다.
각 수열에서 무조건 한 개의 숫자를 골라야하므로, 모든 수열에서 가장 작은 수를 선택합니다.
이후 그 중에 가장 작은 수가 있는 수열에서 하나씩 뒤로 미룹니다.
이 경우 시간 복잡도는 \(O(N M \lg{M})\)입니다.
대신 매 순간 선택된 수 중에서 가장 작은 수와 가장 큰 수를 찾기 위한 알고리즘이 필요하며 이에 따른 시간복잡도가 추가됩니다.
그래도 브루트포스 보다 훨씬 효율적입니다.
아이디어는 준비됐으니 이제 이 방법을 구현할 두 가지 방법을 알아봅시다.
(1) Priority Queue
위의 방법에서 매 순간 선택된 수 중에서 가장 작은 수를 찾기 위한 방법으로 우선순위 큐를 사용할 수 있습니다.
우선순위 큐의 길이는 항상 M이 유지됩니다. 우선순위 큐에 넣는 값은 각 수열에서 단조증가형태이므로 최대값은 넣는 과정에서 관리할 수 있습니다.
최소값은 우선순위 큐에서 하나씩 제거하며 확인할 수 있습니다.
우선순위 큐에서 최소값을 제거할 때, 그 최소값이 어느 수열인지 알아야 하므로 실제 구현할 때에는 수열을 구분할 수 있는 데이터도 함께 우선순위 큐에 넣습니다.
이 과정을 반복하면 위에서 생각한 방법 그대로 구현을 할 수 있습니다.
우선순위 큐를 구현한 최소힙의 heappop과 heappush의 시간 복잡도는 \(O(\lg{N})\)이므로 이 방법의 총 시간 복잡도는 \(O(NM\lg{N})\)입니다.
(2) Two-pointer
최소값과 최대값을 일정한 규칙으로 유지시키며 탐색하는 경우 두 개의 포인터를 사용할 수 있습니다.
이 문제도 매 순간 최소값을 제외해야하고, 또 최대값과의 차이를 계산해야하므로 두 개의 포인터를 사용하여 구현해봅시다.
수열의 개수가 두 개 이상인데 어떻게 두 개의 포인터만 가지고 구현할 수 있을까요?
이를 위해 두 가지 아이디어가 더 필요합니다.
먼저, 모든 수를 하나의 정렬된 수열로 만듭니다. 대신, 각 수가 몇 번째 수열에 속하는지 함께 관리합니다.
그리고, 각 수열에서 숫자가 몇 개 선택되었는지 관리합니다.
초기화(initialization)는 모든 수열에서 1개 이상이 선택될 때까지 오른쪽 포인터(그림에서는 빨간색 포인터)를 오른쪽으로 밉니다.
그리고 반복되는 과정으로, 최소값인 왼쪽 포인터(그림에서는 파란색 포인터)가 속한 수열을 확인하고 한 칸 오른쪽으로 밉니다. 밀기 전 수열에서 선택된 개수를 하나 줄이고, 그 수열에서 선택된 개수가 1 이상이 될 때까지 오른쪽 포인터를 오른쪽으로 밉니다.
더이상 반복할 수 없을 때까지 위 과정을 반복합니다.
이렇게 구현할 경우 시간 복잡도는 \( O(NM\lg{(NM)}) \)이 됩니다.
