#백준_7453 합이 0인 네 정수 - Java

# 분류 : 이진 탐색, 투 포인터 알고리즘

# 백준 1208번 https://ukyonge.tistory.com/38 문제와 비슷하다. 하지만 반복문을 돌려 리스트에 저장해서 풀었을 때는 시간초과가 나서, 입력 받고 나서 계산하여 4개의 배열을 2개의 배열로 나누어 값을 넣어서 계산했더니 통과.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer;   public class p7453 {     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);              } }   Colored by Color Scripter

cs