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

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

 

import sys

# 수의 개수 입력
N = int(sys.stdin.readline())

# 입력된 수들을 저장할 리스트
nums = []

# 수들을 입력받아서 리스트에 저장
for _ in range(N):
    num = int(sys.stdin.readline())
    nums.append(num)

# 오름차순 정렬
nums.sort()

# 가장 큰 수부터 하나씩 선택해서 검사
for i in range(N-1, -1, -1):
    target = nums[i]  # 현재 검사하려는 목표 수 (세 수의 합이 되어야 하는 값)

    # target보다 작은 수들 중에서 두 수의 합과 비교
    for j in range(i-1, -1, -1):  # 두 번째 수 선택
        left = 0
        right = j  # 투포인터 범위는 j까지 (j보다 큰 수는 사용할 수 없음)
        third = nums[j]  # 세 번째 수 (중간 수)

        # 투포인터로 나머지 두 수를 선택
        while left <= right:
            s = nums[left] + nums[right] + third  # 세 수의 합

            if target == s:
                print(target)  # 조건 만족하는 가장 큰 수 출력
                exit(0)        # 바로 종료
            elif s < target:
                left += 1      # 합이 작으면 왼쪽 포인터 증가
            elif s > target:
                right -= 1     # 합이 크면 오른쪽 포인터 감소

O(N^2 log N)의 복잡도로 해결하였다. 

 

더 깔끔하게 해결 한 분이 계셔서 코드를 첨부한다.

import sys
input=sys.stdin.readline

N=int(input())
arr=set()
for _ in range(N):
    arr.add(int(input()))


sums=set()
for i in arr:
    for j in arr:
        sums.add(i+j)

ans=set()
for i in arr:
    for j in arr:
        if i-j in sums:
            ans.add(i)
print(max(ans))

두 수의 합을 미리 저장하여 해결하였다.