삼총사

문제

프로그래머스 131705 - 삼총사

학생들의 정수 번호가 담긴 배열이 주어질 때, 그 중 3명을 뽑아 번호의 합이 0이 되는 조합의 개수를 구하는 문제. (Level 1)

처음 막혔던 부분

3명을 뽑는다는 것 자체를 코드로 어떻게 표현해야 할지가 안 잡혔다. 처음엔 인덱스를 그냥 0, 1, 2처럼 고정해서 생각했는데, 그렇게 하면 배열 전체를 순회하면서 조합을 빠짐없이 만들 수 없다는 게 문제였다.

세 개의 인덱스를 어떻게 움직여야 중복 없이, 순서 겹치지 않게 모든 조합을 만들 수 있는지가 핵심이었다.

어떻게 풀었나

첫 번째 인덱스 i는 0부터 시작하고, 두 번째 인덱스 j는 i보다 항상 뒤에서(i+1부터), 세 번째 인덱스 k는 j보다 항상 뒤에서(j+1부터) 시작하도록 잡으면 같은 조합을 두 번 세거나 순서만 다른 조합을 중복으로 세는 문제가 생기지 않는다는 걸 스스로 정리했다.

그 위에 세 수의 합이 0인지 체크하는 조건만 얹으면 되는 구조.

완성 코드

class Solution {
    public int solution(int[] number) {
        int answer = 0;

        for (int i = 0; i < number.length; i++) {
            for (int j = i + 1; j < number.length; j++) {
                for (int k = j + 1; k < number.length; k++) {
                    if (number[i] + number[j] + number[k] == 0) {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
}

배운 점

• 인덱스 설정 원칙: 중복 없이 조합을 뽑을 때는 뒤 인덱스가 항상 앞 인덱스보다 크게(i < j < k) 잡아야 한다. 이렇게 해야 같은 세 명을 순서만 바꿔서 여러 번 세는 걸 방지할 수 있다.
• 시간복잡도: 겉보기엔 삼중 for문이라 O(n³) 같지만, i<j<k 조건 때문에 실제 반복 횟수는 조합의 수 nC3 = n(n-1)(n-2)/6이다. 배열 길이가 최대 1000이어도 약 1억 6600만 번 수준이라 시간 안에 충분히 통과된다.