문제

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

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution() 함수를 완성하시오

---

정답률: 68%
권장 시간: 30분
권장 시간 복잡도: O(N^2log(N^2))
출제: 월간 코드 챌린지

---

제약 조건

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

---

풀이

1. 배열에서 두 수를 선택하고 이에 대한 합을 구함
2. 1에서 구한 수를 새로운 배열에 저장하고 중복값 제거
3. 배열을 오름차순으로 정렬하고 반환

def solution(numbers):
    answer = []
    # 두 수를 선택하는 모든 경우의 수를 반복문으로 구함
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
        	# 두 수를 더한 결과를 새로운 배열에 추가
            answer.append(numbers[i] + numbers[j])
    # 중복된 값을 제거하고, 오름차순 정렬
    answer = sorted(set(ret))
    return answer

print(solution([2, 1, 3, 4, 1])) # 반환값 : [2, 3, 4, 5, 6, 7]
print(solution([5, 0, 2, 7])) # 반환값 : [2, 5, 7, 9, 12]

---

시간 복잡도

• N은 numbers의 길이
• 이중 반복문으로 모든 원소들에 대해 두 수의 합을 구하는 연산의 시간 복잡도는 O(N^2)
• 이를 set으로 만들 때 시간 복잡도 O(N^2)
• N^2의 데이터 정렬에는 O(N^2log(N^2))의 시간 복잡도가 필요

N = 100이므로 시간 복잡도를 이렇게 해도 문제를 푸는데 큰 영향 x