[월간 코드 챌린지 시즌1] 두 개 뽑아서 더하기

https://programmers.co.kr/learn/courses/30/lessons/68644

코딩테스트 연습 - 두 개 뽑아서 더하기

numbers 배열에서 서로 다른 인덱스의 2 개 숫자를 더해서 만들 수 있는 모든 수를 answer 배열에 오름차순으로 담아 return 하도록 해야한다.

 

풀이1. 이 문제를 보고 바로 떠오른 방법은, numbers 배열에서 2 개를 선택(combination)하고 더한 값을 중복 없이 answer 배열에 저장하는 것이다. 이를 위해서 백트래킹을 이용하였다.

 

[C++]

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

using namespace std;

int sum = 0;
vector<int> arr(2, 0);

bool check(int x, vector<int>& answer)
{
    for (auto& ele : answer)
    {
        if (ele == x)
        {
            return false;
        }
    }
    return true;
}

void dfs(int depth, int start, vector<int>& numbers, vector<int>& answer)
{
    if (depth == 2)
    {
        // sum 계산
        sum = arr[0] + arr[1];

        if (check(sum, answer) == true) //answer 배열에 sum 이 존재하지 않으면
        {
            answer.push_back(sum); // answer 배열에 넣고
        }
        sum = 0; // sum 을 다시 0으로 하고 return
        return;
    }
    else
    {
        for (int i = start; i < numbers.size(); i++)
        {
            arr[depth] = numbers[i];
            dfs(depth + 1, i + 1, numbers, answer);
        }
    }
}

vector<int> solution(vector<int> numbers) {
    vector<int> answer;

    dfs(0, 0, numbers, answer);

    sort(answer.begin(), answer.end());

    return answer;
}

 

풀이2. 다른 사람의 풀이를 구경하다가, 내가 조금 복잡하게 생각한 측면이 있다는 것을 깨달았다. 백트래킹을 사용하지 않아도, 중복을 허용하지 않는 컨테이너인 set 을 이용하면 보다 쉽게 구현할 수 있었다. numbers 배열에서 2개씩 뽑아서 더한 것을 set 컨테이너에 넣어주면 자동으로 중복이 제거되고, answer 에 넣어주면 된다. set, map 은 자동으로 오름차순으로 정렬되므로 별도의 정렬은 필요없다.

 

[C++]

 

#include <string>
#include <vector>
#include <set>

using namespace std;


vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    set<int> s;

    for (int i = 0; i < numbers.size(); i++)
    {
        for (int j = i+1; j < numbers.size(); j++)
        {
            s.insert(numbers[i] + numbers[j]);
        }
    }
    answer.assign(s.begin(), s.end());

    return answer;
}