[백준] 2295번 - 세 수의 합 (파이썬)

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

 

# 세 수의 합
import sys
input = sys.stdin.readline
N = int(input())
arr = [int(input()) for _ in range(N)]
arr.sort()

arr_sum = set()
for x in arr:
    for y in arr:
        arr_sum.add(x+y)


def check():
    global answer
    for i in range(N-1, -1, -1):
        for j in range(i+1):
            if arr[i]-arr[j] in arr_sum:
                answer = arr[i]
                return


answer = 0
check()
print(answer)

 

풀이
 x + y + z = k 일 때, x + y = k - z 임을 이용해서 풀었다.
1. arr_sum : 두 수의 합 (x + y)을 집합에 모두 넣어둔다. (두 수는 중복 가능)
2. check : 탐욕적 접근으로 k가 가장 큰 수부터 오게 끔 역으로 접근
    - k - z 가 arr_sum에 존재한다면 (x + y = k - z), answer는 k를 넣고 return
3. answer 출력

 

N = 1000 이므로 시간 복잡도 O(N^2) 가능

집합을 이용해서 중복 값도 제거하고, 집합의 접근할 때의 시간 복잡도는 O(1)을 이용할 수 있다.

집합은 내부적으로 해시 테이블이 존재해서 arr[i] - arr[j] in arr_sum는 시간 복잡도 O(1)만큼 차지한다.