[Java] 프로그래머스(level-1) - 삼총사

문제 풀이

---

int형 배열 numbers에서 3개의 원소를 뽑아 합이 0일 경우에만 카운트를 하면 되는 문제이다.
간단한 조합공식을 활용해서 3개의 수를 뽑을 수 있다.

조합을 활용해 접근할 수 있는 아이디어를 생각해보자.

• 문제에서 3개의 수를 뽑는다고 정해놨기 때문에 단순하게 반복문을 3번 돌면 된다.
• 뽑은 수를 또 뽑으면 안되니(중복되면 안됨) 앞에서부터 차례대로 뽑으면 된다.

그럼 코드를 작성해보자.

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++;
        }
    }
}

3중 반복문을 통해 첫번째, 두번째, 세번째 수를 자기자신이 아닌 다음 수를 고르면 된다.
> 그렇게 뽑은 3개의 수의 합이 0이 될 때 카운트를 1씩 증가시키면 된다.

작성 코드

---

class Solution {
    public static void main(String[] args) {
        int[] number = {-2, 3, 0, 2, -5};
        // int[] number = {-3, -2, -1, 0, 1, 2, 3};
        // int[] number = {-1, 1, -1, 1};

        long start = System.currentTimeMillis();
        solution(number);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static 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++;
                }
            }
        }

        System.out.println(answer);
        return answer;
    }
}

회고

• 프로그래머스 코딩테스트 연습에 새로운 문제가 추가되어 못참고 바로 풀기 시작했다.
• 백트래킹이나 재귀를 통한 조합 공식으로도 풀어봐야겠다.