[프로그래머스 C++] 두 개 뽑아서 더하기

1차원 배열이 주어지면 그 수에서 두 개를 뽑아서 더해주면 된다. 단 중복을 허용하지 않고 오름차순으로 정렬해야 한다.

 

제한 사항을 보면 numbers의 길이가 100 이하이다. 따라서 이중 포문으로 해줘도

$O(N^2)$의 시간복잡도를 가지기에 중복을 방지하는 stl set을 사용해서 

자기 자신인 i == j 인 경우를 제외하고 전부 넣어준다.

 

이후에 반복문을 모두 돌았다면 answer에 삽입해주면 된다.

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;
 
vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    set<int> s;
    
    int n = numbers.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) continue;
            s.insert(numbers[i] + numbers[j]);
        }
    }
    for (int i : s) answer.emplace_back(i);
    
    return answer;
}