[백준] 2473 - 세 용액 (G4)

https://www.acmicpc.net/problem/2473

2473번: 세 용액

여러가지 방법으로 풀 수 있는 세 용액 문제이다.

나는 처음에 이분탐색을 시도 했다가 막혔는데, 구현을 쓸데없이 복잡하게 하다가 실수를 했던 것 같다.

2시간 고민하다가 다른 이분탐색 풀이 알고리즘을 보고 수정하여 맞았다.

 

이 문제를 투 포인터로 풀 수 있겠다는 생각까진 해봤는데,

구체적으로 어떻게 투 포인터를 써야할 지 떠오르지가 않았다.

그렇게 공부하여 알게된 알고리즘이 3-SUM 알고리즘 이다.

 

---

이분탐색 풀이

---

일단 나는 케이스를 나누었다.

1. 음수 3개로 구성

2. 양수 3개로 구성

3. 양수 1개 음수 2개

4. 양수 2개 음수 1개

 

그 이유는 통으로 이분탐색할 경우 2개를 선택하고, 나머지 하나에 대해 이분탐색을 해야하는데

선택한 2개를 이분탐색 도중 제외하는 방법이 떠오르지 않았기 때문이다.

(즉, mid 값이 미리 골랐던 값과 동일 하면 어떻게 mid 값을 처리할 것인지)

 

제일 직관적인 선택한 2개의 값을 배열에서 뺐다가, 해당 케이스 이후에 다시 배열에 넣고..

이걸 반복하는건 아무리봐도 리스트 특성상 시간이 너무 오래 걸릴 것 같아서 딱히 시도도 안해봤다.

 

그래서 그냥 양수 / 음수 나눠서 고르는 케이스에 대해 이분탐색을 진행해보자고 생각했다.

1, 2 번 케이스는 그리디하게 3개 합의 절댓값이 제일 작은 것을 골라주면 되고,

3, 4 번 케이스 같은 경우, 2개를 골라야 하는 부분에 대해 이중 반복문을 돌고 O(N^2)

나머지 1개를 골라야 하는 부분은 이분탐색으로 2개를 고른 합과 가장 비슷한 것을 골랐다. O(logN)

 

이 알고리즘은 O(N^2logN) 의 시간복잡도를 갖는다.

---

사실 정말 맨 처음에 2시간동안 뻘짓했던 풀이는

양수 2개중 1개를 고르고, 음수 1개를 고른다음, 나머지 양수를 이분탐색으로 찾는(....)

구현하다 실수하기 딱 좋은 복잡한 풀이를 떠올렸다.

왜 이걸 양수 / 음수끼리 묶어서 처리할 생각을 못했을까...ㅋㅋ

 

다른 이분탐색 풀이는 굳이 케이스를 나누지 않고 한번에 하던데 한번 읽어봐야겠다.

대체 어떻게 했을까..

 

이 코드는 python3 로는 시간초과를 받았고, pypy3 로 통과했다. (0.7초 / 1초)

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
if nums[-1] < 0:
    minus = nums[:]
    plus = []
else:
    for i in range(n):
        if nums[i] > 0:
            minus = nums[:i]
            plus = nums[i:]
            break

answer_group = []
minus.sort(reverse=True)

if len(plus) >= 3:
    answer_group.append((plus[0], plus[1], plus[2]))

if len(minus) >= 3:
    answer_group.append((minus[0], minus[1], minus[2]))

if len(plus) >= 2 and minus:
    min_diff = 9999999999999999
    min_comb = []
    for i in range(len(plus)):
        for j in range(i+1, len(plus)):
            s = plus[i] + plus[j]
            start, end = 0, len(minus) - 1
            while start < end:
                mid = (start + end) // 2
                if abs(minus[mid]) >= s:
                    end = mid
                else:
                    start = mid + 1

            if abs(s + minus[end]) < min_diff:
                min_diff = abs(s + minus[end])
                min_comb = (minus[end], plus[i], plus[j])

            if end > 0 and abs(s + minus[end - 1] < min_diff):
                min_diff = abs(s + minus[end - 1])
                min_comb = (minus[end - 1], plus[i], plus[j])

    answer_group.append(min_comb)

if len(minus) >= 2 and plus:
    min_diff = 9999999999999999
    min_comb = []
    for i in range(len(minus)):
        for j in range(i+1, len(minus)):
            s = minus[i] + minus[j]
            start, end = 0, len(plus) - 1
            while start < end:
                mid = (start + end) // 2
                if s + plus[mid] >= 0:
                    end = mid
                else:
                    start = mid + 1

            if abs(s + plus[end]) < min_diff:
                min_diff = abs(s + plus[end])
                min_comb = (minus[i], minus[j], plus[end])

            if end > 0 and abs(s + plus[end-1]) < min_diff:
                min_diff = abs(s + plus[end-1])
                min_comb = (minus[i], minus[j], plus[end-1])

    answer_group.append(min_comb)

#print(answer_group)
answer_group.sort(key=lambda x:abs(sum(x)))
print(*sorted(answer_group[0]))

---

투 포인터 풀이 (3-SUM)

---

더 간단하고 더 빠른 알고리즘이다.

그냥 음수/양수 구분 없이 수를 하나 고르고 O(N)

정렬된 수에 대해 가장 왼쪽에 p1, 가장 오른쪽에 p2 로 포인터를 놓는다.

 

고른 수와 p1, p2 가 나타내는 수를 모두 더해서

합이 0보다 크면 합을 줄어야 하므로 p2 를 왼쪽으로 보내고,

합이 0보다 작으면 합을 늘려야 하므로 p1 을 오른쪽으로 보낸다.

 

이 중간 중간 과정마다 세 수의 합의 절댓값 크기를 0과 비교해서

제일 절댓값이 작은 녀석을 골라주면 된다.

혹시 p1, p2가 미리 앞서 골랐던 수를 가리키면 그냥 그 포인터가 이동하던 방향으로 한번 더 이동시켜 주면 된다.

두 포인터가 합쳐서 배열 하나를 순회하므로 O(N)의 시간복잡도를 갖는다.

 

따라서 총 시간복잡도는 O(N^2) 이다.

 

n = int(input())
nums = list(map(int, input().split()))
nums.sort()


min_diff = 9999999999999999
min_comb = []

for i in range(n):
    n1 = nums[i]
    p1, p2 = 0, n-1
    while p1 != p2:
        if p1 == i:
            p1 += 1
            continue
        if p2 == i:
            p2 -= 1
            continue
        s = n1 + nums[p1] + nums[p2]
        if abs(s) < min_diff:
            min_diff = abs(s)
            min_comb = (n1, nums[p1], nums[p2])

        if s == 0:
            break
        if s > 0:
            p2 -= 1
        else:
            p1 += 1

print(*sorted(min_comb))

더 짧고 간결한 코드이다.

분명 시간복잡도는 충분한데 왜 python3 으로 시간초과가 나고 pypy3 로 0.2초 만에 통과가 되는진 모르겠다