[백준]3151: 합이 0 - JAVA

https://www.acmicpc.net/problem/3151

 

풀이

N개의 숫자들 중 3개를 선택하여 그들의 합을 0으로 만드는 경우의 수를 찾는 문제이다.

 

배열에 숫자들을 저장하여 정렬한다.

 

첫 번째 숫자를 선택하고, 그 다음 숫자를 left, 배열의 끝 숫자를 right로 놓고 left와 right를 조정하여 합이 0이 되는 수를 찾는다.

 

선택한 숫자를 node라고 할 때, `node + arr[left] + arr[right]` 가 0이 되는 경우를 찾아 정답을 증가시킨다.

 

`arr[left]` 와 `arr[right]`가 같은 경우에는 left부터 right까지의 수가 n개라고 할 때 nC2의 조합을 구하는 것과 같다.

 

처음 선택한 수를 0부터 시작하여 증가시키면서 값이 0보다 커질 때까지 실행하면 답을 구할 수 있다.

 

---

 

메모리: 18272KB
시간: 372ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        long answer = 0;
        for (int i = 0; i < n; i++) {
            int node = arr[i];
            if (node > 0) {
                break;
            }

            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = node + arr[left] + arr[right];

                if (sum == 0) {
                    int lCnt = 1;
                    int rCnt = 1;
                    if (arr[left] == arr[right]) {
                        int tmp = right - left + 1;
                        answer += (tmp * (tmp - 1) / 2);
                        break;
                    }

                    while (arr[left] == arr[left + 1]) {
                        left++;
                        lCnt++;
                    }
                    while (arr[right] == arr[right - 1]) {
                        right--;
                        rCnt++;
                    }

                    answer += lCnt * rCnt;
                }

                if (sum > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }

        System.out.println(answer);
    }
}