프로그래머스 [연습문제 / 삼총사](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 131705 삼총사

---

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

문제 설명:

학생들은 각자 정수 번호를 가지고 있으며, 3명의 학생 번호를 더했을 때 0이 되면 삼총사가 됩니다. 정수 배열 number가 주어질 때, 삼총사를 만들 수 있는 방법의 수를 구하는 문제입니다. 배열의 길이는 3 이상 13 이하이고, 각 원소는 -1,000 이상 1,000 이하의 정수입니다. 브루트포스(완전 탐색) 접근 방식으로 모든 3개 조합을 확인해야 합니다.

---

문제 해결 코드

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

int solution(vector<int> number) {
    int answer = 0;
    
    // 배열을 오름차순 정렬하여 조기 종료 최적화 준비
    sort(number.begin(), number.end());
    
    // 첫 번째 학생 선택 (i)
    for(int i = 0; i < number.size() - 2; i++) {
        
        // 두 번째 학생 선택 (j)
        for(int j = i + 1; j < number.size() - 1; j++) {
            int sum = number[i] + number[j];
            
            // 두 수의 합이 이미 양수면, 이후 더 큰 수를 더해도 0이 될 수 없음
            if(sum > 0) break;
            
            // 세 번째 학생 선택 (k)
            for(int k = j + 1; k < number.size(); k++) {
                int totalSum = number[i] + number[j] + number[k];
                
                // 세 수의 합이 양수면, 이후 더 큰 수를 더해도 0이 될 수 없음
                if(totalSum > 0) break;
                
                // 세 수의 합이 정확히 0이면 삼총사 발견
                if(totalSum == 0) answer++;
            }
        }
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 브루트포스(완전 탐색) 방식으로 모든 3개 조합을 확인합니다. 배열을 먼저 정렬한 후, 조기 종료(early termination) 기법을 활용하여 불필요한 연산을 줄입니다. 정렬된 배열에서 두 수의 합이나 세 수의 합이 양수가 되면, 그 이후의 더 큰 수들과 더해도 0이 될 수 없으므로 반복을 중단합니다.
• 구현 세부사항:
  • 배열을 오름차순으로 정렬하여 최적화 기반을 마련합니다.
  • 3중 반복문으로 서로 다른 인덱스 i, j, k를 선택합니다 (i < j < k).
  • number[i] + number[j]가 0보다 크면 내부 반복문을 중단합니다.
  • number[i] + number[j] + number[k]가 0보다 크면 가장 내부 반복문을 중단합니다.
  • 세 수의 합이 정확히 0이면 카운터를 증가시킵니다.
• 시간/공간 복잡도: 시간 복잡도는 O(n³)이며, 최악의 경우 모든 3개 조합을 확인합니다. 하지만 정렬과 조기 종료 최적화로 실제 실행 시간은 크게 단축됩니다. 공간 복잡도는 O(1)로 추가 메모리를 거의 사용하지 않습니다. n의 최대값이 13이므로 13 ⋅ 12 ⋅ 11 / 6 = 286회의 조합 검사로 충분히 빠릅니다.

---

실행 예시

테스트 케이스 1:

입력: number = [-2, 3, 0, 2, -5]

실행 과정:

• 정렬 후: [-5, -2, 0, 2, 3]
• 삼총사 조합 1: -5 + 2 + 3 = 0
• 삼총사 조합 2: -2 + 0 + 2 = 0

출력: 2

테스트 케이스 2:

입력: number = [-3, -2, -1, 0, 1, 2, 3]

실행 과정:

• 정렬 후: [-3, -2, -1, 0, 1, 2, 3]
• 삼총사 조합: (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-3, 1, 2), (-2, -1, 3)

출력: 5

---

결과

정렬과 조기 종료 최적화를 통해 효율적으로 문제를 해결했습니다. n의 최대값이 13으로 작기 때문에 O(n³) 시간 복잡도도 충분히 빠르게 동작합니다. 만약 n이 더 크다면 투 포인터나 해시맵을 활용한 O(n²) 알고리즘을 고려할 수 있습니다.

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