[백준] 2473번 세 용액 _ Python

[초기 접근 방법]

1. 완전탐색
     N * (N-1) * (N-2) / 3! = 200억

 

2. 이분탐색
     2개를 임의로 선정하여 sum, sum과 가까운 k 값 찾기
     N * (N-1) * logN = 3억

 

두 방법 모두 시간초과가 난다.

 

 

 

[생각]

투포인터 유형이라고 생각을 했는데, 어떻게 접근하고 구현해야 될 지 몰라 풀이를 참고했다.

 

 

1) 용액을 오름차순으로 정렬

 

2) for i in range(N)

     i : 한 개의 점을 고정

     i + 1 : 시작점(s)

     N : 끝점(e)

 

3) (i + s + e) 가 최소가 되는 값을 찾기 위해

     s와 e를 계속 이분탐색 한다.

 

 

최근에 들었던 생각이 알고리즘 자체가

무언가 다익스트라와 같은 최단경로 알고리즘도 그러하고, 수학 같은 문제에서

머리 속으로 생각하는 개념적인 풀이를,

자료구조는 어떻게 쓰고 반복은 최소화하며 조건을 어떻게 처리하는 등 논리적으로 풀어내는 연습이고 모르는 유형의 문제라도

바로 정답을 참고하지 않고 일단은 나만의 논리식으로 풀어내고 어떤 점이 틀렸고, 더 최적화할 수 있는지 비교해보는 것이 필요할 듯하다.

 

 

 

[코드]

# 풀이 시간 : 40분 + 30분
# 시간복잡도 : O(N^2)
# 공간복잡도 : O(N)
# 참고 : https://kdr0407.tistory.com/33

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

lst.sort()

minSum = float('inf')
ans = []

# i 고정, i+1 시작점, N-1 끝점
for i in range(len(lst)):
    s = i+1
    e = N-1

    # 투포인터
    while s < e:
        val = lst[i] + lst[s] + lst[e]
        if minSum > abs(val):
            minSum = abs(val)
            ans = [lst[i], lst[s], lst[e]]

        # 이분탐색과 비슷
        # 총합이 음수인 경우, s++
        if val < 0:
            s += 1
        # 총합이 양수인 경우, e--
        else:
            e -= 1

print(*ans)

 

 

 

 

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

2473번: 세 용액