두 개 뽑아서 더하기

문제

문제 해석

- 뽑아서 사용한다면 조합을 이용하므로 next_permutation()을 사용한다 -> algorithm 헤더 포함
-- 조합용 별도의 배열이 필요하다(오름차순을 위해 마지막 2개의 원소를 1로 변경한다)
-- 조합으로 사용할 것이므로 do-while로 반복
-- 조합용 배열의 원소값이 1이면 더하여 나온 숫자를 중복 제거를 위해 set<int>에 insert
- vector<int>로 반환하기 위해서 set<int>의 원소를 순회하여 push_back()
- sort()를 이용하여 오름차순 정렬 수행

 

코드

#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numbers) {
    size_t Size = numbers.size();
    vector<int> Combination(numbers.size(), 0);
    Combination[Size - 2] = Combination[Size - 1] = 1;    

    set<int> uniqueNumbers;
    do 
    {
        int Result = 0;
        for (int IDX = 0; IDX < Combination.size(); ++IDX)
        {
            if (Combination[IDX] == 1)
            {
                Result += numbers[IDX];
            }
        }

        uniqueNumbers.insert(Result);
    } while (next_permutation(Combination.begin(), Combination.end()));
    
    vector<int> answer;
    for(auto Number : uniqueNumbers)
    {
        answer.push_back(Number);
    }
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

 

다른 사람의 풀이

next_permutation을 사용하는 것과 set을 사용하면 어차피 오름차순이므로 sort를 사용하지 않음.

1. next_permutation을 사용하지 않고 i번 인덱스와 i+1번 ~ 끝 인덱스의 것을 더하는 반복문을 사용하면 어차피 set이므로 중복은 허용되지 않기 때문에 동일한 동작을 함(이는 숫자를 2개만 뽑아서 더하기 때문에 가능함)

2. set은 오름차순으로 정렬되기 때문에 sort를 굳이 사용할 필요가 없음.

3. vector container의 assign을 사용하면 set의 iterator를 사용하는 것으로 한번에 vector를 초기화 할 수 있음.