프로그래머스 [연습문제 / 두 개 뽑아서 더하기](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 68644 두 개 뽑아서 더하기

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/68644

문제 설명:

정수 배열 numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 구하는 문제입니다. 결과는 중복 없이 오름차순으로 정렬하여 반환해야 합니다. 배열의 길이는 2 이상 100 이하이고, 각 원소는 0 이상 100 이하입니다. 조합과 정렬을 활용한 간단한 구현 문제입니다.

---

문제 해결 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    
    // 서로 다른 두 인덱스의 조합을 모두 시도
    for(int i = 0; i < numbers.size() - 1; i++) {
        for(int j = i + 1; j < numbers.size(); j++) {
            // 두 수의 합을 결과 배열에 추가
            answer.push_back(numbers[i] + numbers[j]);
        }
    }
    
    // 오름차순 정렬
    sort(answer.begin(), answer.end());
    
    // 중복 제거: unique는 중복을 뒤로 이동시키고 새로운 끝 위치를 반환
    answer.erase(unique(answer.begin(), answer.end()), answer.end());
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 조합(Combination) 생성과 중복 제거입니다. 이중 반복문으로 서로 다른 인덱스의 모든 조합을 생성합니다. i를 0부터 n-2까지, j를 i+1부터 n-1까지 순회하여 중복 없이 모든 쌍을 선택합니다. 두 수의 합을 배열에 저장한 후 정렬하고, unique + erase 조합으로 중복을 효율적으로 제거합니다.
• 구현 세부사항:
  • 이중 반복문에서 j는 i+1부터 시작하여 같은 인덱스를 두 번 선택하지 않습니다.
  • 모든 가능한 합을 answer 벡터에 추가합니다(중복 포함).
  • sort 함수로 오름차순 정렬합니다.
  • unique 함수는 정렬된 배열에서 연속된 중복을 제거하고, 중복되지 않은 원소들을 앞쪽에 배치합니다.
  • unique는 새로운 논리적 끝을 가리키는 반복자를 반환하며, erase로 그 이후의 쓰레기 값을 제거합니다.
  • unique는 정렬된 배열에서만 올바르게 동작하므로 반드시 sort 후에 사용해야 합니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n² + m log m)입니다. 여기서 n은 numbers 배열의 길이, m은 생성된 합의 개수(최대 n ⋅ (n-1) / 2)입니다. 이중 반복문이 O(n²), 정렬이 O(m log m), unique와 erase가 O(m)입니다. 공간 복잡도는 O(m)으로, answer 벡터에 최대 m개의 합을 저장합니다.

---

실행 예시

테스트 케이스 1:

입력: numbers = [2, 1, 3, 4, 1]

실행 과정:

• 가능한 모든 조합의 합:
  • 2+1=3, 2+3=5, 2+4=6, 2+1=3
  • 1+3=4, 1+4=5, 1+1=2
  • 3+4=7, 3+1=4
  • 4+1=5
• 정렬 전: [3, 5, 6, 3, 4, 5, 2, 7, 4, 5]
• 정렬 후: [2, 3, 3, 4, 4, 5, 5, 5, 6, 7]
• 중복 제거 후: [2, 3, 4, 5, 6, 7]

출력: [2, 3, 4, 5, 6, 7]

테스트 케이스 2:

입력: numbers = [5, 0, 2, 7]

실행 과정:

• 가능한 모든 조합의 합:
  • 5+0=5, 5+2=7, 5+7=12
  • 0+2=2, 0+7=7
  • 2+7=9
• 정렬 전: [5, 7, 12, 2, 7, 9]
• 정렬 후: [2, 5, 7, 7, 9, 12]
• 중복 제거 후: [2, 5, 7, 9, 12]

출력: [2, 5, 7, 9, 12]

---

결과

이중 반복문과 STL 알고리즘을 효과적으로 활용한 간결한 솔루션입니다. 원본 코드는 이미 최적의 구조로 작성되어 있으며, sort와 unique + erase 조합으로 중복 제거를 우아하게 처리했습니다. 특히 unique 함수는 정렬된 배열에서만 동작하므로 반드시 sort 후에 사용해야 한다는 점이 중요합니다. n이 최대 100으로 작기 때문에 O(n²) 시간 복잡도도 충분히 효율적입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!