🔵 문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/68644
🔵 문제 설명
정수 배열이 주어지고, 배열에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 solution() 함수를 완성하세요.
❗주의해야 할 점
- 반환 배열은 오름차순으로 정렬되어 있어야 한다.
- 반환 배열은 중복값을 허용하지 않는다.
- 서로 다른 인덱스에 있는 두 개의 수를 뽑을 땐 어떻게 해야 하는가?
💡 선택 자료 구조와 이유
Set 자료구조를 선택하였다.
Set 자료구조는 기본적으로 중복을 허용하지 않는 자료구조이며, 데이터 삽입 시 데이터를 오름차순으로 자동 정렬해 준다.
(Set은 균형 이진 트리로 구성되어 있어 트리 구조를 통해 정렬 상태를 유지한다.)
💡 서로 다른 인덱스에 있는 두 개의 수 뽑기
말 그대로 서로 다른 인덱스에 있는 두 개의 수를 뽑으면 된다. 이때, 무의미한 중복 선택을 피하기 위하여 다음과 같이 뽑는다.

🔵 코드
#include <string>
#include <vector>
#include <set>
using namespace std;
vector<int> solution(vector<int> numbers) {
// 문제에서 데이터 중복을 허용하지 않고, 저장 데이터를 정렬해야 함.
// 따라서 set 자료 구조를 사용한다.
set<int> ret;
// 서로 다른 인덱스에 있는 두 개의 수를 뽑는다.
// 중복 선택 없이 발생할 수 있는 모든 경우의 수를 찾음.
// set은 데이터 삽입 시 자동 정렬한다.
for(int i = 0; i < numbers.size(); i++)
for(int j = i + 1; j < numbers.size(); j++)
ret.insert(numbers[i] + numbers[j]);
// vector를 set으로 변환한다.
vector<int> answer(ret.begin(), ret.end());
return answer;
}
🔵 시간 복잡도
N은 numbers의 길이이다. 이중 반복문을 통해 모든 원소에 대해 두 수의 합을 구하는 연산의 시간 복잡도는 N^2이며, N^2개의 데이터를 set에 삽입하므로 시간복잡도는 O(N^2 * logN)이 된다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 2 "행렬의 곱셈" (0) | 2025.04.22 |
|---|---|
| [C++] Programmers Lv. 1 "모의고사" (0) | 2025.04.18 |
| [C++] Boj 18808 스티커 붙이기 (0) | 2025.03.05 |
| [C++] Boj 15683 감시 (0) | 2025.02.20 |
| [C++] Boj 16987 계란으로 계란치기 (0) | 2025.02.17 |