[C++] Programmers Lv. 1 "두 개 뽑아서 더하기"

🔵 문제 링크

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)이 된다.