백준 7453 합이 0인 네자리 수 java

문제 소개 www.acmicpc.net/problem/7453

내용

• 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.
• A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

해결 방법

아이디어

n이 4000이다. 브루트 포스로 구한다 생각했을 때, 4개의 배열이 있으므로 4000^4(256,000,000,000,000) 연산이 필요할 것 같다.

이와 비슷한 문제인 한 배열에서의 경우를 생각해봤다.

정렬 이후에 front와 back 포인터를 두고 하나씩 전진해가며 경우의 수를 찾았었다.

이번의 경우도 비슷할 것 같다. 

 

A,B 배열을 모든 경우의 수를 뽑으면 약 16,000,000개가 되고 그 수는 

C,D 배열도 동일하게 하면 16,000,000 배열 2개다.

AB 배열을 first라 했고, CD 배열을 second라 한 뒤 각각 배열을 정렬했. 

이후 투 포인터 처럼 계산했다.

실제 풀이 코드

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[][] array = new int[4][n];

        for (int i = 0; i < n; i++) {
            String[] split = br.readLine().split(" ");

            for (int j = 0; j < 4; j++) {
                array[j][i] = Integer.parseInt(split[j]);
            }
        }

        int[] first = new int[n*n];
        int[] second = new int[n*n];

        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                first[index] = array[0][i] + array[1][j];
                second[index] = array[2][i] + array[3][j];
                index++;
            }
        }

        Arrays.sort(first);
        Arrays.sort(second);

        int head = 0;
        int back = second.length - 1;
        long answer = 0;

        while(head < first.length && back >= 0){
            int firstValue = first[head];
            int secondValue = second[back];

            int sum = firstValue + secondValue;
            if (sum == 0) {
                int firstValueCount = 0;
                int secondValueCount = 0;

                while(head < first.length && firstValue == first[head]){
                    firstValueCount++;
                    head++;
                }

                while(back >= 0 && secondValue == second[back]){
                    secondValueCount++;
                    back--;
                }
                answer += (long) firstValueCount * (long) secondValueCount;
            }
            else if(sum > 0) {
                back--;
            } else {
                head++;
            }
        }
        System.out.println(answer);
    }
}

결과

AB배열, CD배열이 16,000,000이라서 정렬시 시간 초과가 날것이라고 생각했다.

하지만 시간초과가 나지않았고 주어지 시간이 12초라서 그런것인가 의문이다.

 

그리고 AB배열, CD배열을 ArrayList를 사용했더니 시간초과가 발생했다. 확실히 n이 천만이 넘어가면

컬렉션 객체보다 배열을 사용하는 것이 시간을 많이 아낄수 있나보다.