[ 프로그래머스 [ 월간코드챌린지 ] 두 개 뽑아서 더하기 ] (C++)

프로그래머스의 두 개 뽑아서 더하기(월간코드챌린지) 문제이다.

[ 문제풀이 ]

주어진 배열에서, 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해서 만들 수 있는 모든 수를 구해야 하는 문제이다.

그럼 먼저 주의해야 할 한 가지 부분에 대해서 알아본 후, 본격적으로 풀이를 알아보자.

#1. 중복된 수에 대한 처리

예를 들어서 , 배열이 [ 1 , 2 , 3 , 4 ] 가 있다고 가정해보자.

이 때, 2번 숫자와 3번 숫자를 뽑아서 더했다고 가정해보자.

그럼, 2 + 3 = '5' 라는 결과가 나오게 된다.

이 상태에서 , 1번 숫자와 4번 숫자를 뽑아서 더해보자. 그럼, 1 + 4  = '5'라는 결과가 나오게 된다.

위의 내용대로만 보면, '5'라는 결과는 2번 나오게 되지만, 실제 결과에서 '5'는 한 번만 나오게 된다.

즉 ! 중복된 숫자는 한 번만 처리를 해줄 수 있어야 한다.

따라서 이 부분을 위해서 본인은 bool형의 1차원 배열을 하나 선언해 주었다.

bool Visit[A] = true 의 의미는 "A라는 숫자는 이미 기존에 한번 나온적이 있습니다." 라는 것을 의미하고

bool Visit[A] = false 의 의미는 "A라는 숫자는 아직 나온적이 없는 숫자입니다." 를 의미한다.

또한, 주어진 배열의 모든 수는 100이하의 수라고 했으므로, 2개를 뽑았을 때 나올 수 있는 가장 큰 수는 100 + 100 = 200 이기 때문에, Visit배열의 크기를 210으로 설정해주었다.

#2. 정답 도출하기

단순 2중 for문으로 모든 인덱스 간의 결과를 더해주면 된다.

주어진 배열의 길이가 최대 100이기 때문에, 모든 경우를 탐색한다 하더라도, 100 * 100 = 10000으로 시간적 부담이 없는 연산 횟수이다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool Visit[210];
 
vector<int> solution(vector<int> numbers) 
{
    vector<int> answer;
    for (int i = 0; i < numbers.size(); i++)
    {
        for (int j = i + 1; j < numbers.size(); j++)
        {
            int Result = numbers[i] + numbers[j];
            if (Visit[Result] == false)
            {
                Visit[Result] = true;
                answer.push_back(Result);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}