[알고리즘] Python -n개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는 ?

n개의 수를 입력 받아서 두 수를 뽑아 합이 가장 클 때는 ?

방법 1)

완전탐색으로 풀이할 때

조합을 이용하여 그중 합이 가장 큰 것을 출력한다

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

from itertools import combinations

sumlist = []
sum = 0
for combi in combinations(list, 2):
    sum = combi[0] + combi[1]
    sumlist.append(sum)
    sumlist.sort(reverse=True)

print(sumlist[0])

 

 

-> 시간제한 1초, 입력 2<= N <= 1,000,000 일 경우

위의 방법을 사용하면 빅오표기법으로 보면 O(N제곱) -> 시간초과 

"구현하기 전에 시간초과를 생각하고 해야 시간이 낭비되지 않음"

 

 

 

방법 2)

정렬한 후 가장 큰 두수를 뽑아 더해준다.

정렬(sort)하는 시간복잡도 = O(NlogN)

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

list.sort(reverse=True)
sum = list[0]+list[1]

print(sum)

 

 

방법 3)

for문을 사용하여 제일 큰거 구하고 2번째 for문 사용하여 두번째 큰 수 구한다

n + n -> O(N)

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

max1, max2 = 0
for item in list:
    if max1 > item:
        max1 = max1
    else:
        max1 = item

list.remove(max1)
for item in list:
    if max2 > item:
        max2 = max2
    else:
        max2 = item

print(max1+max2)

 

 

 

 

 

틀린 부분이나 수정사항, 좋은 방법 아시는 분은 알려주세욤....