백준(BOJ) 7453 : 합이 0인 네 정수 (JAVA)

문제링크 : https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

이 문제에서 모든 경우의 수를 다 구해본다면, 그 때의 시간복잡도는 O(N^4)이다. N의 최댓값이 4000밖에 되지 않기 때문에 그렇게 푸는 것도 가능할 것 같긴 했으나(해보진 않음;;) 더 효율적인 방법을 알기에 그렇게 하지 않았다.

 

1. A와 B의 합, C와 D의 합에 대한 모든 경우의 수를 각각 subsetAB, subsetCD라는 새로운 배열에 저장한다. 이 때 각각의 subset의 크기는 N * N이 될 것이다.

2. 두 subset을 오름차순으로 정렬한다.

3. 두 subset의 합이 0일 때의 경우의 수를 센다. 이 때 투포인터 알고리즘을 사용한다.

 

투포인터 알고리즘에 대해 자세히 설명하면,

일단 left = 0, right = N * N - 1(subset의 가장 마지막 인덱스)로 초기화한다.

left는 subsetAB의 인덱스를 가리킬 것이고, right는 subsetCD의 인덱스를 가리킬 것이다.

 

현재 각각의 subset은 오름차순으로 정렬되어있다. subsetAB[left] + subsetCD[right]의 값이 0보다 작다면 어떻게 해야할까? left를 증가시켜야한다. 현재의 subsetCD는 가장 큰값이므로 더 증가시킬수가없다. 반대의경우에는 right를 감소시키면된다. 이런식의 탐색을 통해 훨씬 적은 횟수의 비교를 통해 네 배열의 합이 0인 모든경우의수를 구할 수있다. 투포인터를 사용했을 시 시간복잡도는 O(N^2)이다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        int[] d = new int[n];
        
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
            c[i] = Integer.parseInt(st.nextToken());
            d[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] subsetAB = getSubset(n, a, b);
        int[] subsetCD = getSubset(n, c, d);
        
        Arrays.sort(subsetAB);
        Arrays.sort(subsetCD);
        
        int left = 0;
        int right = n * n - 1;
        long cnt = 0;
        
        while(left < n * n && right >= 0) {
            int leftVal = subsetAB[left];
            int rightVal = subsetCD[right];
            int tmp = leftVal + rightVal;
            
            if(tmp < 0) {
                while(++left < n * n && subsetAB[left] == leftVal) {
                    // do nothing
                }
            } else if(tmp > 0) {
                while(--right >= 0 && subsetCD[right] == rightVal) {
                    // do nothing
                }
            } else {
                long leftCnt = 1;
                long rightCnt = 1;
                
                while(++left < n * n && subsetAB[left] == leftVal) {
                    leftCnt++;
                }
                
                while(--right >= 0 && subsetCD[right] == rightVal) {
                    rightCnt++;
                }
                
                cnt += leftCnt * rightCnt;
            }
        }
        
        System.out.println(cnt);
    }
 
    private static int[] getSubset(int n, int[] a, int[] b) {
        int[] subset = new int[n * n];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                subset[i * n + j] = a[i] + b[j];
            }
        }
        
        return subset;
    }
}