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

문제 설명

정수 배열 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]

풀이

순열을 사용한 조합 구하는 방법을 사용했습니다.

nCr = numbers.size() C 2 

조합을 구하기 위해서 보조 수열이 필요합니다.

1.보조 수열은 numbers사이즈 크기로 생성하고, 0으로 초기화 합니다.

2. 2개만 뽑아야 하니, 보조 수열의 맨 뒤에서 부터 2개의 원소를 1로 변경합니다.

3.결과 값을 저장하는 벡터의 오름차순 정렬, 중복 제거를 마지막에 적용시킵니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    
    int len = numbers.size();
    vector<int> visit(len, 0);
    visit[len-1] = 1;
    visit[len-2] = 1;
    
    int sum = 0;
    do{
        for(int i = 0; i < len; i++){
            if(visit[i] != 0){
                sum += numbers[i];
            }
        }
        answer.push_back(sum);
        sum = 0;
        
    }while(next_permutation(visit.begin(), visit.end()));
    
    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    
    return answer;
}

다른 방법

중복을 허용하지 않는 set을 사용하여

이중 for문으로 접근하는 방법입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    set<int> st;
    for(int i = 0;i<numbers.size();++i){
        for(int j = i+1 ; j< numbers.size();++j){
            st.insert(numbers[i] + numbers[j]);
        }
    }
    answer.assign(st.begin(), st.end());
    return answer;
}