프로그래머스_월간 코드 챌린지 시즌1_두 개 뽑아서 더하기

1. 문제

출처 : 프로그래머스

2. 소스코드

def solution(numbers):     answer = set()     for i in range(len(numbers)):         for j in range(i+1,len(numbers)):             answer.add(numbers[i] + numbers[j])     answer = list(answer)     answer.sort()     return answer

 

3. 고찰

1) 알고리즘

인덱스를 이용해서 두 수를 뽑았다.

더한 수를 answer에 넣었는데, answer는 set을 사용하였다.

set은 list와 다르게 중복 원소는 한 개만 저장하는 특징이 있다. 하지만 sort를 할 수 없어서 answer를 다시 list로 변경한 후 오름차순으로 정렬하였다.

 

2) 시간복잡도

이중 for문을 사용하기 때문에 O(N^2)

sort함수는 O(N logN)

최종적으로 이 코드의 시간복잡도는 O(N^2 + N logN) = O(N^2)이다.