[백준] 2467. 용액 - 파이썬

[Gold V]

 

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

2467번: 용액

 

풀이 1과 풀이 2 모두 AC(통과)가 가능한 코드입니다.

 

풀이 1

일단, 모든 경우의 수를 다 따져본다면(Brute-Force),

_NC₂ 이기 때문에, (N * (N-1)) / 2 => O(N^2) 정도의 Time Complexity로 풀 수 있게 됨.

당연히 이 방법은 아닐 테고,

 

일단 문제를 보자마자 직감적으로 생각난 것은 Two Pointer였다.

그런데 일반적인 two pointer의 느낌으로 간다면, index를 0, 1에서 출발하든, 0, N-1에서 출발하든 분명 놓치는 부분이 생길 것이라고 생각했고, 실제로 구현해 보니 예제 input도 통과하지 못했다.

 

그래서 분명 모든 용액에서의 가장 0에 가까워지는 다른 용액을 하나씩 찾아야 답을 낼 수 있을 것이라고 생각했다.

(용액이 A, B, C, D, E라면, A를 넣었을 때 가장 0에 가까워 질 수 있는 용액을 찾고, 똑같이 B를 넣었을 때 가장 0에 가까워 질 수 있는 용액을 찾고... 이렇게 5개의 용액 모두 자신과 같이 넣었을 때 0에 가까워질 수 있는 다른 용액이 하나씩은 나와야 한다고 생각함)

그래서 다시 생각해본 것이, Binary Search로 계산하면 O(NlogN)까지는 줄일 수 있으니 풀리지 않을까? 라고 생각했다.

N개의 용액마다, O(logN)인 Binary Search로 검색하므로, O(NlogN).

 

그렇게 AC.

N = int(input())
sol = list(map(int, input().split()))

result = [1000000000, 1000000000]
for i in range(N-1):
    lo = i+1
    hi = N-1

    while lo+1 < hi:
        mid = int((lo+hi)/2)
        if sol[i]+sol[mid] < 0:
            lo = mid
        else:
            hi = mid

    temp = []
    if abs(sol[i]+sol[lo]) < abs(sol[i]+sol[hi]):
        temp = [sol[i], sol[lo]]
    else:
        temp = [sol[i], sol[hi]]

    if abs(sum(temp)) < abs(sum(result)):
        result = temp
    if sum(result) == 0:
        break

print(*result)

 

풀이 2

풀고 나서 확인해 보니, 처음 생각했던 것처럼 Two Pointer로도 풀이할 수 있었다.

코드도 거의 다 제대로 짰는데, 조건을 실수로 반대로 쓰는 바람에 계속 WA가 나왔던 것.

알맞게 고쳐서 다시 제출해 보니 AC.

N = int(input())
sol = list(map(int, input().split()))

i = 0
j = N-1

result = [1000000000, 1000000000]
while i < j:
    if abs(sol[i]+sol[j]) < abs(sum(result)):
        result = [sol[i], sol[j]]

    if sol[i]+sol[j] > 0:
        j -= 1
    elif sol[i]+sol[j] < 0:
        i += 1
    else:
        break

print(*result)