[프로그래머스] 두 개 뽑아서 더하기 (Lv.1)

---

문제 링크

---

프로그래머스 - 두 개 뽑아서 더하기

문제 설명

---

정수 배열 numbers에서 서로 다른 인덱스의 두 수를 뽑아 더한 모든 경우의 수를 구한다.
결과는 중복을 제거하고 오름차순으로 정렬하여 반환한다.

예) [2, 1, 3, 4] → [3, 4, 5, 6, 7]

내 풀이

---

이중 반복문으로 모든 쌍을 탐색하는 완전탐색(Brute Force) 방식으로 접근했다.
i와 j = i + 1로 서로 다른 인덱스의 두 수를 뽑아 더한 뒤 set에 삽입했다.
set은 중복을 자동으로 제거하고 오름차순으로 정렬해주므로, 마지막에 vector로 변환만 하면 된다.

#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]);
        }
    }
    
    for(int temp : s)
    {
        answer.push_back(temp);
    }
    
    return answer;
}

시간복잡도 분석

---

이중 반복문: O(n²)
set 삽입은 O(log n)이므로 전체는 O(n² log n)

문제 조건상 numbers의 길이는 최대 100이므로, n = 100일 때 약 10,000번 연산 → 제한 시간 내 충분히 통과 가능하다.

후기

---

for(set::iterator iter = s.begin(); iter != s.end(); iter++) answer.push_back(*iter);

옛날에 풀어보고 다른 곳에서 방법을 찾다가 발견한 방법인데, 이런 간단한 줄로도 해결할 수 있다는 걸 알았다. (참고. 얘는 O(k)이라고 한다. 여기서 k는 set의 원소의 개수를 의미한다.)

• algorithm
• codingtest
• bruteforce