[백준] 2295. 세 수의 합 - 파이썬

[Gold IV]

 

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

2295번: 세 수의 합

 

풀이

일단 초견에서 생각한 것은 -

1. x, y, z를 pointer로, two pointer처럼 풀이하면 되려나?
2. 집합을 Set이나 List로 저장한다면, 세 수의 합이 집합에 포함되는 지 확인하는 Time Complexity가 O(N)이고, 포함 여부 확인은 반복문 안에서 계속해서 하게 될 텐데. => Hashing이 가능한 Dictionary를 이용해 집합을 저장하여 Time Complexity를 O(1)로 만들어야겠다.

이 두 가지였다.

 

모든 x, y, z에 대해서 Brute-Force로 처리한다면, O(N^3)의 Time Complexity, 원소가 1,000개이므로 - 약 10^9개, 10억개니까.. 당연히 TLE가 날 것이라 생각.

y를 고정하고, x, z를 two pointer 느낌으로 값에 따라 index를 늘리고 줄이며 해결해볼까 했지만, y를 고정하더라도, x, z를 모든 원소에 대해 반복해야 되므로, 불가능.

 

곰곰이 생각해보다, x+y+z = k 이므로, x, y를 정하는 데에 O(N^2)으로,

k 또한 U의 원소이므로, z, k를 정하는 데에도 O(N^2)으로 반복하며, k-z가 미리 구해 놓은 x+y 리스트에 존재하는 지 확인.

두 반복 모두 O(N^2)이므로, 총 Time Complexity도 O(N^2)으로 해결된다!

N = int(input())

# 오름차순 정렬된 dictionary
s = []
for _ in range(N):
    s.append(int(input()))

s = {i: 1 for i in sorted(s)}

u = s.keys()

sum_xy = dict()
for x in u:
    for y in u:
        sum_xy[x+y] = 1

result = []
for z in u:
    for k in u:
        if sum_xy.get(k-z, -1) == 1:
            result.append(k)

print(max(result))