[Programmers] 두 개 뽑아서 더하기*

 

Description

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예

numbers	result
[2, 1, 3, 4, 1]	[2, 3, 4, 5, 6, 7]
[5, 0, 2, 7]	[2, 5, 7, 9, 12]

 

 

권장 시간 복잡도  $O(N^2log(N^2))$

---

풀이

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

 

아주 간단한 문제다. 2가지의 핵심은 중복을 허용하지 않는다는 것과 반복문을 어떻게 처리할 것인지이다.

우선 입출력 예시의 result 개수를 확인해보면 2번째 예시에서는 N=4이므로 6개의 정답이 나와야 하는데 5개뿐이다.

이는 7의 중복을 허용하지 않았기 때문임을 간단히 알 수 있다.

반복문의 경우 nested 반복문을 i+1부터 설정하면 되지만 시간 복잡도상 0부터 설정하는 것과 $O(N^2)$으로 비슷하므로 설명하지 않겠다.

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/68644

프로그래머스