백준 7453 합이 0인 네 정수 [java]

20 Jun 2022 in Develop / Solving

중간에서 만나기.

그냥 백준을 둘러보다가 ‘중간에서 만나기’ 라는 알고리즘 분류를 보게 되었다. 이게 뭔가 싶어서 인터넷에 검색해보았고, 검색해본 김에 한문제 풀어보려고 한다.

문제 분석

• 중간에서 만나기
• 네 개의 배열이 주어지고, 각각의 배열들에 들어있는 숫자들이 주어진다.
• 이 배열에서 숫자를 하나씩 뽑아서 0을 만들 때, 0이 만들어지는 경우의 수를 구하여라.

입력조건

배열의 크기 N
N줄에 걸쳐 {
 네 개의 배열의 원소 A[i] B[i] C[i] D[i]
}

풀이과정

• 중간에서 만나기로 배열을 두 개로 압축한다.
  • 이 배열들의 최대 크기는 16000000이 된다.
• 만들어진 두 배열 중에 한 배열만 정리한다.

추가

나는 이게 분할정복이랑 비슷하다고 생각하는데, 이걸 분할정복으로 보는지 아닌지 모르겄다.

• arraylist쓰면 시간초과 난다… 이렇게 시간차이가 클줄이야..

ans를 int형으로 받으면 시간초과가 난다.

16000000 크기의 배열 두개를 교차해서 정답을 찾다 보니, 자연스럽게 int의 범위를 넘어가는 것 같다.

전체 코드

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

public class BJ7453_합이0인네정수 {
    static int size;
    static int[][] sums;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        int[][] map = new int[4][N];
        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int d = 0; d < 4; d++)
                map[d][i] = Integer.parseInt(st.nextToken());
        }
        // 입력 완료.
        
        size = N*N;
        sums = new int[2][size];

        // 합치기.
        for(int d = 0; d < 2; d ++){
            for(int i = 0; i < N; i++)
                for(int j = 0; j < N; j++)
                    sums[d][i*N + j] = map[d][i] + map[d+2][j];
        }
        Arrays.sort(sums[1]);

        long ans = 0;
        // 이분탐색으로 답 찾기.
        for(int n : sums[0]){
            long u = uppersearch(-1 * n);
            long l = lowersearch(-1 * n);
            ans += u-l;
        }

        System.out.print(ans);
    }
    public static int uppersearch(int target){
        int l = 0;
        int r = size;
        
        while(l < r) {
            int mid = (l + r) / 2;
            int num = sums[1][mid];

            if (target >= num) l = mid + 1;
            else r = mid;
        }
        return l;
    }
    public static long lowersearch(int target){
        int l = 0;
        int r = size;
        
        while(l < r) {
            int mid = (l + r) / 2;
            int num = sums[1][mid];

            if (target <= num) r = mid;
            else l = mid + 1;
        }
        return l;
    }
}