삼총사

작성일: 2024-10-16

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

문제에 대한 내용

문제 설명

한국중학교에 다니는 학생들은 각자 정수 번호를 갖고 있습니다. 이 학교 학생 3명의 정수 번호를 더했을 때 0이 되면 3명의 학생은 삼총사라고 합니다. 예를 들어, 5명의 학생이 있고, 각각의 정수 번호가 순서대로 -2, 3, 0, 2, -5일 때, 첫 번째, 세 번째, 네 번째 학생의 정수 번호를 더하면 0이므로 세 학생은 삼총사입니다. 또한, 두 번째, 네 번째, 다섯 번째 학생의 정수 번호를 더해도 0이므로 세 학생도 삼총사입니다. 따라서 이 경우 한국중학교에서는 두 가지 방법으로 삼총사를 만들 수 있습니다.

한국중학교 학생들의 번호를 나타내는 정수 배열 number가 매개변수로 주어질 때, 학생들 중 삼총사를 만들 수 있는 방법의 수를 return 하도록 solution 함수를 완성하세요.

제한 조건

• 3 ≤ number의 길이 ≤ 13
• -1,000 ≤ number의 각 원소 ≤ 1,000
• 서로 다른 학생의 정수 번호가 같을 수 있습니다.

입출력 예

number	result
[-2, 3, 0, 2, -5]	2
[-3, -2, -1, 0, 1, 2, 3]	5
[-1, 1, -1, 1]	0

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

입출력 예 #2

• 학생들의 정수 번호 쌍 (-3, 0, 3), (-2, 0, 2), (-1, 0, 1), (-2, -1, 3), (-3, 1, 2) 이 삼총사가 될 수 있으므로, 5를 return 합니다.

입출력 예 #3

• 삼총사가 될 수 있는 방법이 없습니다.

접근 방식

1. 서로 다른 n 개에서 3개를 구해야 하는 문제이다. 순서에 상관이 없기 때문에 조합이다.
2. 배열과 숫자의 크기가 크지 않기 때문에 삼중for문으로 풀었다.

결과

소스 코드

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

        for (int i=0; i<number.length-2; i++){
            for (int j=i+1; j<number.length-1; j++){
                sum = number[i] + number[j];
                for (int k=j+1; k<number.length; k++){
                    answer = sum + number[k] == 0 ? answer + 1 : answer;
                }
            }
        }

        return answer;
    }
}

결과 이미지

다른 접근 방식

재귀를 이용해서 푸는 방식이 있다.

class Solution {
    public int solution(int[] number) {
        return combination(number, 0, 0, 0, 3);
    }

    private int combination(int[] number, int start, int count, int sum, int r) {
        if (count == r) {
            return sum == 0 ? 1 : 0;
        }

        int result = 0;
        for (int i = start; i < number.length; i++) {
            result += combination(number, i + 1, count + 1, sum + number[i], r);
        }
        return result;
    }
}

1. 재귀 함수를 호출한다. (combination)
2. 재귀 함수가 시작 지점(start)부터 for문을 돌린다. (처음부터)
3. sum에 현재 위치의 값을 더한다.
4. 돌면서 만약 현재 재귀 횟수가 3과 일치한다면 (삼총사라면), 현재의 sum값을 비교해서 result에 더한다.

알게 된 점

없음