[프로그래머스] 월간 코드 챌린지 시즌1 Lv1. 두 개 뽑아서 더하기

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

드디어 기말고사도 끝나고 겨울방학을 맞이했다 >< 그리고 방학동안 인턴을 하게 되었다!

학기 중에 알고리즘 스터디를 했었는데,
그 때의 감을 잃어버릴까봐 오랜만에 문제를 풀어봤다
오랜만이니까 쉬워보이는 것으로 풀었다..ㅎㅎ

그래서 스케치도 매우 간단하다
먼저 문제를 정리하면서 보니까 조합을 이용하면 되겠다는 생각이 들어서 간단하게만 적었다!

문제 아이디어가 우선이라 생각되서 조합 재귀함수는 구글링을 통해 얻었다
(참고: https://ansohxxn.github.io/algorithm/combination/)

생각했던 것처럼 조합으로 풀리긴 했는데
이후 '다른 사람의 풀이'에서 보니까 'set'이라는 것을 이용해서 푼 사람이 있어서
나도 다시 set으로 풀어봤다

set은 이번에 처음 알게 됐는데,
원소의 중복을 허용하지 않고, 삽입 순서에 상관없이 정렬되어서 이 문제에 딱 알맞는 것 같다
유일한 원소를 가지기 때문에 수학적으로는 집합의 의미라고 한다
균형 이진 트리로 구현되어 빠른 탐색에도 적합하다고 한다

set을 이용하여 푼다는 건,,
일일히 두 수의 조합을 확인하고 더한 값을 넣어주어야 한다는 건데
그럼 numbers의 배열을 중첩 for문으로 순회해야 한다는 점에서 이것도 시간초과 괜찮으려나 싶었다
근데 시뮬레이션 해보니까 인덱스가 커질수록 순회해야하는 숫자의 개수도 적어져서 괜찮을 것 같았다

배운 점

1. set

• 중복 원소 허용하지 않음 (- 중복 허용하려면 multiset 사용해야 함)
• 삽입 순서에 상관없이 오름차순 정렬됨
• 균형이진트리로 구현됨

2. 향상된 for문

• set에 대해 알아보다가 알게 됐는데, 이런 for문이 있는지 처음 알았음

for(int i:s)
    {
        answer.push_back(i);
        cout<<i<<" ";
    }

set을 이용하니까 훨씬 짧아져서 좋다
역시 많이 알면 알수록 좋구나..!

1. 조합 이용 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
void Combination(vector<int> &answer, vector<int> arr, vector<int> comb, int r, int index, int depth)
{
    int tmp = 0;

    if(r==0)
    {
        for(int i=0; i<comb.size(); i++)
        {
            tmp += comb[i];         
        }

        auto it = find(answer.begin(), answer.end(), tmp);
        if (it == answer.end())
        {
            answer.push_back(tmp);
        }
        tmp = 0;
    }
    else if(depth==arr.size())
    {
        return;
    }
    else
    {
        comb[index] = arr[depth];
        Combination(answer, arr, comb, r - 1, index + 1, depth + 1);
        Combination(answer, arr, comb, r, index, depth + 1);
    }
}

vector<int> solution(vector<int> numbers) {
    int r = 2;
    vector<int> comb(r);
    vector<int> answer;
    Combination(answer, numbers, comb, r, 0, 0);

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

    return answer;
}

2. set 이용 풀이

#include <iostream>
#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()-1; i++)
    {
        for(int j=i+1; j<numbers.size(); j++)
        {
            s.insert(numbers[i] + numbers[j]);
        }
    }

    for(int i:s)
    {
        answer.push_back(i);
        cout<<i<<" ";
    }
    cout<<endl;

    return answer;
}