[백준 7453번] 합이 0인 네 정수 (Java 풀이)

백준알고리즘 7453번 : 합이 0인 네 정수 (Solved.ac 난이도 Gold2)

 

 

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

7453번: 합이 0인 네 정수

 

 

 

첫번째로 간과한 부분은 12초가 꽤 러프하다고 생각하여 단순 계산으로 시도해본 것이고,

두번째로 간과한 부분은 속도를 높이기 위해 투 포인터 방식을 사용했으나

동일한 연산에 대하여 곱셈이 아니라 덧셈으로 count를 해준 것이다.

예를들어 AxB 배열에 13이 3개, CxD 배열에 -13이 3개 있다고 하면

본래는 3x3으로 9개로 count하는 것이 맞는데 나는 단순히 3개, 3개를 더하여 6개로 count해버려서 12% 쯤에서 오류가 발생했다.

해당 내용만 보완해주었더니 맞출 수 있었다.

 

풀이 과정

---

1. 배열 4개(A, B, C, D)를 정의하고, 각 배열마다 값을 입력 받는다.
2. AxB배열, CxD배열을 정의하고, 각각 오름차순으로 정려한다.
3. 투 포인터를 사용하여 탐색하면서 count하되,
   동일한 값이 나온 경우 동일 값의 갯수만큼 곱한 갯수를 count에 추가한다.

 

소스 ▽

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

public class Main { // [Gold2] 7453번 : 합이 0인 네 정수
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long cnt = 0;
        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());
        }

        long[] mltplX = new long[N * N];
        long[] mltplY = new long[N * N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                mltplX[N * i + j] = A[i] + B[j];
                mltplY[N * i + j] = C[i] + D[j];
            }
        }
        Arrays.sort(mltplX);
        Arrays.sort(mltplY);

        int x = 0;
        int y = N * N - 1;
        while (x < N * N && y >= 0) {
            if (mltplX[x] + mltplY[y] > 0) {
                    y--;
            } else if (mltplX[x] + mltplY[y] < 0) {
                    x++;

            } else {
                long xc=1, yc=1;
                while (true) {
                    if (x + 1 < N * N && mltplX[x] == mltplX[x + 1]) {
                        xc++;
                        x++;
                    } else {
                        break;
                    }
                }
                while (true) {
                    if (y - 1 >= 0 && mltplY[y] == mltplY[y - 1]) {
                        yc++;
                        y--;
                    } else {
                        break;
                    }
                }
                cnt+=xc*yc;
                x++;
                y--;
            }
        }

        System.out.println(cnt);
    }
}