[프로그래머스] 삼총사 자바

https://school.programmers.co.kr/learn/courses/30/lessons/131705

프로그래머스

 

문제

주어진 정수 배열 중 3개의 숫자를 활용해서 세 숫자의 합이 0이되는 케이스의 수를 구하시오.

제한사항

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

접근

주어진 배열 numbers를 순회하여 세 값의 합이 0이 되는 케이스를 구하는 로직을 작성

public int solution(int[] number) {
        int answer = 0;
        for (int value : number) {
            for (int j = 1; j < number.length; j++) {
                for (int k = 2; k < number.length; k++) {
                    if (value + number[j] + number[k] == 0) answer++;
                }
            }
        }
        return answer;
    }

발견된 문제

1.중복 카운트 발생
(i, j, k) 순서만 다른 조합을 서로 다른 경우로 세고 있습니다.예: (1, 2, 3)과 (3, 2, 1)을 다른 조합으로 처리합니다.
조합(Combination)이 아닌 순열(Permutation) 방식으로 동작합니다.
2.인덱스 범위 오류
j와 k의 시작 인덱스가 고정되어 있어 같은 요소를 반복 선택할 수 있습니다.
예: i=0, j=1, k=1 → number[1]을 두 번 선택하게 됩니다.
3.불필요한 연산
i, j, k가 모두 같은 인덱스를 가리킬 수 있어 의미 없는 계산이 포함됩니다.

수정

public int solution2(int[] number) {
        int answer = 0;
        int n = number.length;
        //첫번째 ~ 마지막에서 3번째 까지 순회
        for( int i = 0; i < n -2; i++){
            // i 다음 숫자 ~ 마지막에서 두번째 까지 순회
            for(int j = i + 1; j < n - 1; j ++){
                // j 다음 숫자 ~ 마지막까지 순회
                for(int k = j + 1; k < n; k ++){
                    if(number[i] + number[j] + number[k] == 0) answer ++;
                }
            }
        }
        return answer;
    }

알게된 점

1. 배열을 순회 할 때, 불필요한 중복을 제거하기 위해선 시작 인덱스와 종료 인덱스 범위를 조정하여 피할 수 있다.