[Java] 백준 7453번 - 합이 0인 네 정수

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

7453번: 합이 0인 네 정수

[문제]

 

[풀이]

4개 조합을 생성하여 계산을 하는 방법은 시간초과가 나와서 고민하다가 아래의 블로그를 참고하여 풀이하였습니다.

https://skdltm117.tistory.com/49

[백준] 7453번 - 합이 0인 네 정수 (java)

A와 B, C와 D를 미리 계산하여 preSum[][] 저장하여 투포인터 방식으로 해결하면 되는 문제였습니다.

• data[][]에 A,B,C,D의 숫자들을 저장합니다. 
• data[0] X data[1] , data[2] X data[3] 을 preSum[0], preSum[1]에 저장합니다.
• 투포인터 방식을 사용하기 위해 preSum[0]와 preSum[1]을 Arrays.sort()를 통해 정렬합니다.
• preSum[0]은 왼쪽부터,  preSum[1]은 오른쪽부터 탐색하며 합이 0이 되는 갯수를 세어갑니다.
• 만약 같으 수가 있다면, 그 숫자의 갯수를 세서 곱해주는 과정을 진행합니다.

 

[코드]

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

public class Main {
    static int N;
    static long answer = 0;
    static int[][] data;
    static int preSum[][];
    static StringTokenizer st;

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

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

        preSum = new int[2][N * N];
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                preSum[0][count] = data[i][0] + data[j][1];
                preSum[1][count++] = data[i][2] + data[j][3];
            }
        }
        Arrays.sort(preSum[0]);
        Arrays.sort(preSum[1]);
        int first = 0;
        int second = preSum[0].length - 1;

        int end = N * N;
        while (first < end && 0 <= second) {
            int sum =  preSum[0][first] + preSum[1][second];
            int firstCnt =1;
            int secondCnt = 1;
            if (sum == 0) {
                while (first <= end - 2 && preSum[0][first] == preSum[0][first + 1]) {
                    firstCnt++;
                    first++;
                }
                while (0 < second && preSum[1][second] == preSum[1][second - 1]) {
                    secondCnt++;
                    second--;
                }
                answer += (long) firstCnt * secondCnt;
            }

            if (sum < 0) {
                first++;
            } else{
                second--;
            }
        }
        System.out.println(answer);
    }
}