처음에 N 제한이 1000 인 것을 보지 않고, 엄청 쉬운 문제라 생각하고 삼 중 for 문으로 접근했습니다. 결과는 시간초과…

이런 식으로 trial & error 하지 말고 고민해서 한 번에 좋은 결과를 얻어야 할텐데… 안 좋은 습관은 고치기 어려운 것 같습니다.

이 문제의 정해는 이진 탐색입니다.

| max(a,b,c) – min(a,b,c) |

위 수식의 값을 가장 작게 하는 a, b, c를 찾는 문제로 치환할 수 있는데, 일 차원적인 풀이는 삼 중 for 문입니다.

• 모든 a, 모든 b, 모든 c에 대해 위의 수식을 계산하고, 그 값 중 가장 작은 것을 해로 취득

물론 모든 경우의 수를 다 해보는 풀이이기 때문에 반드시 답을 얻을 수 있다는 보장은 있으나, 그 시간 복잡도는 O(n^3)입니다.

이진 탐색의 경우 사고 과정은 아래와 같습니다.

• a,b,c의 최댓값과 최솟값의 절대값 차가 가장 작으려면? -> a, b, c간의 차가 작아야 한다.
• 그렇다면
  • a중 하나(i)를 선택
  • i와 가장 근접한 b 중 하나(j)를 선택
  • i와 가장 근접한 c 중 하나(k)를 선택
  • | max(i,j,k) – min(i,j,k) | 계산 후 결과 업데이트

여기까지 고민한 후 풀이를 진행했을 때 당연히 맞을 것이라 생각했지만 결과는 ‘틀렸습니다.’ 였습니다.

이는 생각에 허점이 있었기 때문인데요. i와 가장 근접한 j를 선택할 때 j가 i보다 크게 되면, k를 선택할 때 기준 값이 틀어지기 때문에 가장 근접한 값들을 구할 수 없다는 점입니다.

이점을 해결하기 위해, 사고를 아래와 같이 다시 하였습니다.

• a중 하나(i)를 선택
• i와 같거나, 작으면서 가장 근접한 b 중 하나(j)를 선택
• i와 같거나, 작으면서 가장 근접한 c 중 하나(k)를 선택
• | max(i,j,k) – min(i,j,k) | 계산 후 결과 업데이트

• b중 하나(i)를 선택
• i와 같거나, 작으면서 가장 근접한 c 중 하나(j)를 선택
• i와 같거나, 작으면서 가장 근접한 a 중 하나(k)를 선택
• | max(i,j,k) – min(i,j,k) | 계산 후 결과 업데이트

• c중 하나(i)를 선택
• i와 같거나, 작으면서 가장 근접한 a 중 하나(j)를 선택
• i와 같거나, 작으면서 가장 근접한 b 중 하나(k)를 선택
• | max(i,j,k) – min(i,j,k) | 계산 후 결과 업데이트

위와 같이 풀이하지 않고도, 기준값을 업데이트하면서 진행할 수도 있을 것 같은데, 왠지 누락되는 케이스가 발생할 것 같아 위와 같이 처리하였네요. ( 다른 사람들의 풀이를 보아도 위처럼 푼 분들이 많더라구요. )

이렇게 풀이했을 때의 시간복잡도는 O(n*log(2, n))이 되게 됩니다. O(n^3)에서 획기적인 개선이 되었다고 볼 수 있겠네요. (물론 이진 탐색을 하기 전에 값을 정렬하는 과정이 수반되나, 정렬 알고리즘은 통상 n*log(2, n)에 떨어지니 무시하였습니다.)

이처럼 값을 찾아야 하는 케이스에서는 순차 탐색보다는 이진 탐색을 활용하는 것이 효율적입니다. 앞으로 다른 문제들도 많이 접하게 될 텐데, 이진 탐색으로 문제를 접근하는 습관을 들여야겠습니다.

import sys


def b_search(x: int, arr: []):
    start = 0
    end = len(arr) - 1
    while True:

        p = (start + end) // 2
        if start == p:
            if p == end:
                return arr[p]
            else:
                return arr[p]

        if arr[p] == x:
            return x
        elif arr[p] < x:
            start = p
            continue
        elif arr[p] > x:
            end = p
            continue


input = sys.stdin.readline

t = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

penalty = 1000000000 * 2

for i in a:
    j = b_search(i, b)
    k = b_search(i, c)
    penalty = min(penalty, abs(max(i, j, k) - min(i, j, k)))

for i in b:
    j = b_search(i, c)
    k = b_search(i, a)
    penalty = min(penalty, abs(max(i, j, k) - min(i, j, k)))

for i in c:
    j = b_search(i, a)
    k = b_search(i, b)
    penalty = min(penalty, abs(max(i, j, k) - min(i, j, k)))

print(penalty)