[프로그래머스/C++] ㅡ LV1 - 두 개 뽑아서 더하기

문제

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

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

풀이

#include <vector>
#include <algorithm>

using namespace std;

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 x = numbers[i] + numbers[j];
            bool flag = false;
            for (int k=0; k<answer.size(); k++) {
                if (answer[k] == x) {	// 더한 값이 겹칠 때
                    flag = true;
                    break;
                }
            }
            if (flag == false) {	// 겹치지 않을 때
               answer.push_back(x);
            }
        }
    }
    sort(answer.begin(),answer.end());
    return answer;
}

개념

vector 로 만들어지는 일차원 배열에 값 대입 시 .push_back() 을 사용한다.

answer[0] = 1; 이런 식으로 대입하려 하면 오류가 발생한다.

특이한 점은, vector로 만들어지는 이차원 배열은 그런 대입이 가능하다.

 

vector의 멤버 함수를 사용해 간단히 정렬할 수 있다.

.begin()과 .end()를 사용한다.

---

풀이

 

모든 가능한 수만큼 짝을 만들어야한다.

2중 for문을 사용하면 가능하다.

중첩이 되지 않게 하기 위해 j는 i+1로 초기화 했다.

 

이제 문제는 더한 값이 동일한 경우이다.

2중 for문을 거치면 [3,5,6,3,4,5,2,7,4,5] 가 나오는데, 구해야하는 답은 [2,3,4,5,6,7] 이다.

 

새로운 값을 받을 때, answer 배열의 값들을 탐색해서 값이 있으면 대입하지 않는다.

이를 위해 flag 변수를 사용한다.

 

배열에 값들이 다 들어오면, sort를 사용해 오름차로 정렬하면 된다.

 

※ 3중 for문이므로 시간초과를 걱정했다.

테스트 7에서 0.27ms의 꽤 큰 시간이 걸렸다.