Cooper's devlog

[문제를 처음 접했을 때]

이번 문제는 '합이 0인 네 정수 문제' 입니다.

문제를 간단히 설명드리면 말그대로 합이 0일 때 a,b,c,d의 조합 갯수를 구하는 문제 입니다.

 처음 문제를 보고 생각한 접근 방법은 반복문을 이용한 완전탐색(Brute Force)를 생각했습니다.하지만, 입력의 크기가 4000이므로 시간 복잡도가 O(N^4)인 비효율적인 시간 복잡도가 발생합니다. 다른 접근법을 생각해야 합니다. 이 정도 연산은 컴퓨터에겐 괜찮지만 문제를 해결 못하는 답답함에 고통 받습니다;;

 이를 개선하기 위해서는 투포인터(Two Pointer)을 이용해야 합니다. 투포인터(Two Pointer)은 아래 블로그에 잘 정리되어 있기 때문에 하단에 링크를 들어가셔서 내용 보시는 것을 추천하고 밑에 단계별 코드 흐름에 대해 설명하도록 하겠습니다!

[투포인트를 통한 접근]

투포인트를 이용한 로직 구현은 이렇습니다.

1. AB의 합의 배열을 구한다.

2. CD의 합 배열을 구한다.

3. AB, CD 배열을 정렬한다.

4. AB배열과 CD의 합이 0인 경우를 counting한다.

아래 코드를 분리해서 설명드리겠습니다.

[전체 코드]

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

public class Main {
    static int arr[][];
    static long AB[], CD[];
    static int N;
    static long count=0;

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N][4];
        AB = new long[N*N];
        CD = new long[N*N];
        StringTokenizer st;

        int index=0;

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            arr[i][3] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                AB[index] = arr[i][0] + arr[j][1];
                CD[index] = arr[i][2] + arr[j][3];
                index++;
            }
        }

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

        int leftIndex = 0;
        int rightIndex = N*N-1;

        while(leftIndex< N*N && rightIndex>=0){
            long left_val = AB[leftIndex];
            long right_val = CD[rightIndex];

            if(left_val + right_val == 0){
                long left_count = 0;

                while(leftIndex<AB.length && AB[leftIndex]==left_val){
                    left_count++;
                    leftIndex++;
                }

                long right_count = 0;

                while(rightIndex >= 0 && CD[rightIndex] == right_val){
                    right_count++;
                    rightIndex--;
                }

                count += right_count * left_count;

            }
            if(left_val + right_val < 0){
                leftIndex++;
            }

            if(left_val + right_val > 0){
                rightIndex--;
            }
        }
        System.out.println(count);
    }

}

[단계별 문제 풀이]

먼저 선언된 주된 변수 및 배열에 대해 설명드리겠습니다.

arr[][]  : abcd의 데이터 배열//arr[0] = A, arr[1] = B, arr[2] = C, arr[3] = D
AB[]	 : AB의 합 배열
CD[] 	 : CD의 합 배열
N 	 : abcd 인덱스 갯수
count 	 : 합이 0이 되는 경우의 수

1. AB의 합의 배열을 구한다.

2. CD의 합 배열을 구한다.

        int index=0;

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
            arr[i][2] = Integer.parseInt(st.nextToken());
            arr[i][3] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                AB[index] = arr[i][0] + arr[j][1];
                CD[index] = arr[i][2] + arr[j][3];
                index++;
            }
        }

 입력값을 배열에 추가한 후, 이중 for문을 통해 AB의 합과 CD의 합을 배열에 추가합니다.

3. AB, CD 배열을 정렬한다.

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

java util class에 존재하는 Arrays library를 이용해서 배열을 오름차순 정렬하도록 합니다.

(정렬에 별도의 comparator를 사용하지 않으면 기본적으로 오름차순 정렬이 됩니다.)

4. AB배열과 CD의 합이 0인 경우를 counting한다.

먼저 이 경우는 헷갈릴 수도 있으니 간단히 로직에 대해 설명드리겠습니다.

예제1를 경우, AB와 CD를 정렬 시 아래와 같이 정렬합니다.

  AB 	-99	-95	-90	-90	-86 ....
  CD					.... 101	104	118	119	133

 AB의 경우 -99(왼쪽 끝 인덱스)부터 시작, CD의 경우는 133(오른쪽 끝 인덱스)으로 시작합니다. - 최적 인덱스 찾기

(1) AB + CD > 0 경우, CD의 양수 값이 크다는 것을 의미하므로 CD 인덱스를 왼쪽으로 한칸 이동합니다.

(2) AB + CD < 0 경우, AB의 음수 값이 크다는 것을 의미하므로 AB의 인덱스를 오른쪽으로 한칸 이동합니다.

(3) AB + CD = 0 경우, 0인 경우를 발생했으므로 어느 범위까지 합이 0이 되는지를 탐색합니다.

(1) AB + CD > 0 경우, CD의 양수 값이 크다는 것을 의미하므로 CD 인덱스를 왼쪽으로 한칸 이동합니다.

            if(left_val + right_val > 0){
                rightIndex--;
            }

(2) AB + CD < 0 경우, AB의 음수 값이 크다는 것을 의미하므로 AB의 인덱스를 오른쪽으로 한칸 이동합니다.

            if(left_val + right_val < 0){
                leftIndex++;
            }

(3) AB + CD = 0 경우, 0인 경우를 발생했으므로 어느 범위까지 합이 0이 되는지를 탐색합니다.

            if(left_val + right_val == 0){
                long left_count = 0;

                while(leftIndex<AB.length && AB[leftIndex]==left_val){
                    left_count++;
                    leftIndex++;
                }

                long right_count = 0;

                while(rightIndex >= 0 && CD[rightIndex] == right_val){
                    right_count++;
                    rightIndex--;
                }

                count += right_count * left_count;

            }

0일 경우에 주변을 탐색해서 0일 때의 AB 값이 다른 인덱스에도 있는지 탐색하고,

CD의 경우에도 0이 되는 다른 인덱스가 있는지를 탐색합니다.

위의 코드는 같은 값이 존재해야 같은 결과가 나온다는 기준으로 로직을 작성한 것입니다.

(4)이 로직을 모든 경우의 수를 탐색하기 위해 while문에 해당 조건을 이용하여 탐색하도록 합니다.

while(leftIndex< N*N && rightIndex>=0)

AB의 시작 인덱스인 leftIndex는 0부터 합의 모든 경우(N^2)을 순방향으로 탐색하게 되고,

CD의 시작 인덱스인 rightIndex는 반대로 역방향으로 탐색하여 두 조건이 모두 만족하는 모든 경우의 수를 탐색합니다.

부분적인 로직을 설명했고 아래에 전체 코드를 확인하시면 다음과 같습니다.

[결과]

결과를 보면 많은 메모리 영역을 사용한 것으로 확인됩니다. 아마 모든 입력 값과 AB 합과 CD의 합을 배열에 저장해서  많은 메모리를 차지한 것으로 예상됩니다. 그리고 시간 복잡도는 O(N^2)으로 문제를 접근했기 때문에 무리없이 결과를 통과하지 않았나 생각합니다ㅎㅎ

[Reference]

<Two Pointer 정리>

<문제>