[백준 7543] 합이 0인 네 정수 / 자바 / 투포인터

#문제         

레벨: G2
알고리즘: 투포인터
풀이시간: 1시간
힌트 참조 유무: 유

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

 

---

#문제 풀이        

✔ 풀이법

4개의 배열을 각각 조회하면 시간초과가 발생하므로 A와 B 원소의 합이 C와 D 원소의 합이 부호만 다르고 절대값이 같은 경우를 찾으면된다.여기서 의아한 사람들이 있을 거다. 엥 a+b  = - (c+d) 조합만 고려하면 모든 경우의 수를 찾지 못하지 않나? a+c = -(b+d)라던지 a+d = -(c+b) 의 조합을 고려해야지 않나?

아니다. 한 가지의 조합만 고려해도 모든 경우의 수를 알 수 있다. 예시를 들어보겠다.

위와 같은 배열이 있을 때  a+b  = - (c+d)의 경우의 수만 구해보겠다. 

a+b가 (1+4=5), (1+5=6), (2+4=6), (2+5=7)의 경우의 수가 있다.그럼 c+d의 합이 a+b의 -를 찾아야 하니 -5,-6,-7의 경우의 수를 찾아야 한다.c+d가 -5가 되는 경우의 수   { (-1,-4) }

c+d가 -6가 되는 경우의 수   { (-1,-5), (-2,-4)}

c+d가 -7가 되는 경우의 수   { (-2, -5) }

가 이렇게 된다. 

 

정답은

a+b가 5가 되는 경우의 수  x c+d가 -5가 되는 경우의 수  

+

a+b가 6이 되는 경우의 수  x c+d가 -6이 되는 경우의 수

+

a+b가 7이 되는 경우의 수  x c+d가 -7이 되는 경우의 수

이므로

(1x1) + (2 x 2) + (1 x 1) = 6이다.

 

이제 

 a+c = -(b+d)의 경웅의 수를 살펴 위와 같다는 것을 증명하겠다.

a+c의 경우의 수는 { (1,-1), (1, -2), (2,-1), (2,-2) } 인 경우의 수가 있다.

그럼 b+d의 합이 a+c의 -를 찾아야 하니 0,1,-1의 경우의 수를 찾아야 한다.

 b+d 가 0이 되는 경우의 수   { (4,-4) , (5,-5)}

 b+d 가 1이 되는 경우의 수   { (5,-4)}

 b+d 가 -1이 되는 경우의 수   { (4, -5) }

가 된다.

 

 a+c 가 0이 되는 경우의 수  x  b+d 가 0이 되는 경우의 수  

+

 a+c 가 1이 되는 경우의 수  x  b+d 가 -1이 되는 경우의 수

+

 a+c 가 -1가 되는 경우의 수  x  b+d 가 1이 되는 경우의 수

이므로

(2x2) + (1 x 1) + (1 x 1) = 6이다.

 

똑같이 6으로 똑같다. 에이.. 그러면 둘이 구했던 경우의 수가 다르니 정답이 6으로 같은 게 아니라 6 + 6 해야 되는 거 아니야? 아니다. 구했던 조합을 살펴보자. (파란색이 왼쪽 조합이다.)

AB CD일 때

(1,4,-1,-4)    (1,5,-1,-5)  (1,5,-2,-4),  (2,4,-1,-5)  (2,4,-2,-4)  (2,5,-2,-5)이다.

AC BD일 때는

(1,4,-1,-4)    (1,5,-1,-5)  (1,5,-2,-4),  (2,4,-1,-5)  (2,4,-2,-4)  (2,5,-2,-5)이다.

보시다시피 조합을 달리해서 구하더라도 결과값은 같다.

 그래서 우리는 A+B = -(C+D) 조합만 구할 것이다.

 

☝🏻 해시 맵

원소의 합이 key, 합의 개수가 value인 맵을 만든다. A와 B 원소의 합에 −1을 곱한 값을 C와 D 원소의 합에서 찾고 각 개수를 곱해준다.
하지만 시간초과가 발생했다.

 

✌🏻 이분 탐색

A와 B 원소의 합에 −1을 곱한 값을 C와 D 원소 합 배열에서 찾는다. 중복이 가능하므로 upper bound와 lower bound를 사용하여 해당 개수를 더한다.

 

🤟🏻 투 포인터

두 개의 포인터 중 하나는 왼쪽에서, 다른 하나는 오른쪽에서 시작한다.
A, B 합 배열의 원소와 C, D 합 배열의 원소를 더해 0이 되는 곳을 찾는다.
원소의 중복이 존재하기 때문에 두 배열에서 현재 원소와 동일한 값을 갖는 원소 개수를 센 뒤 두 값을 곱한다.

 

---

#풀이 코드      

투 포인터 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static long[] A;
    static long[] B;
    static long[] C;
    static long[] D;

    static long findByTwoPointer() {
        long[] AB = new long[n * n];
        long[] CD = new long[n * n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                AB[i * n + j] = A[i] + B[j];
                CD[i * n + j] = C[i] + D[j];
            }
        }

        Arrays.sort(AB);
        Arrays.sort(CD);

        long count = 0;

        //2개의 배열에 4개의 포인터(AB왼,AB오,CD왼,CD오)를 쓰는 게 아니라
        //2개의 배열에 2개의 포인터(AB왼,CD오)를 쓰는 거다
        int l = 0, r = n * n - 1;
        while (l < n * n && r >= 0) {
            long sum = AB[l] + CD[r];

            if (sum < 0) {
                l++;
                continue;
            }

            if (sum > 0) {
                r--;
                continue;
            }

            long lCount = 1;
            l++;
            //아래는 AB =  -CD인 경우이다.
            
            
            //AB조합에 같은 숫자가 있다면 그 수만큼 CD조합이랑 곱해줘야 하므로 
            //동일한 숫자를 카운트 하며 포인터를 옮긴다.
            while (l < n * n && AB[l] == AB[l - 1]) {
                lCount++;
                l++;
            }

            //CD조합에 같은 숫자가 있다면 그 수만큼 AB조합이랑 곱해줘야 하므로 
            //동일한 숫자를 카운트 하며 포인터를 옮긴다.
            long rCount = 1;
            r--;
            while (r >= 0 && CD[r] == CD[r + 1]) {
                rCount++;
                r--;
            }

            count += lCount * rCount;
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        A = new long[n];
        B = new long[n];
        C = new long[n];
        D = new long[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            A[i] = Long.parseLong(st.nextToken());
            B[i] = Long.parseLong(st.nextToken());
            C[i] = Long.parseLong(st.nextToken());
            D[i] = Long.parseLong(st.nextToken());
        }

        System.out.println(findByTwoPointer());
        br.close();
    }
}