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

BOJ

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

yujinkimkim 2023. 8. 26. 14:33

7453번: 합이 0인 네 정수

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

www.acmicpc.net

package baekjoon;

import java.util.*;
import java.io.*;

public class b7453 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		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++) {
			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());
		}
		
		int AB[] = new int[n*n];
		int CD[] = new int[n*n];
		
		int idx = 0;
		for(int i = 0 ; i < n; i++) {
			for(int j = 0 ; j < n ; j++) {
				AB[idx] = A[i] + B[j];
				CD[idx++] = C[i] + D[j];
			}
		}
		Arrays.sort(AB);
		Arrays.sort(CD);
		
		long ans = 0;
		int left = 0;
		int right = n*n-1;

		while(left < n*n && right >= 0) {
			int tmp = AB[left] + CD[right];
			if(tmp < 0) {
				left++;
			} else if(tmp > 0) {
				right--;
			} else {
				long leftCnt = 1;
				long rightCnt = 1;
				while(left+1 < n*n && AB[left]==AB[left+1]) {
					left++;
					leftCnt++;
				}
				left++;
				while(right-1 >= 0 && CD[right]==CD[right-1]) {
					right--;
					rightCnt++;
				}
				ans += leftCnt*rightCnt;
				right--;
			}
		}
		bw.write(ans+"");
		bw.close();
	}

}

package baekjoon;

import java.util.*;
import java.io.*;

public class b7453 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		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++) {
			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());
		}
		
		Map <Integer, Integer> map = new HashMap<>();
		for(int i = 0 ; i < n; i++) {
			for(int j = 0 ; j < n ; j++) {
				if(!map.containsKey(A[i]+B[j])) {
					map.put(A[i]+B[j],1);
				}
				else {
					map.put(A[i]+B[j], map.get(A[i]+B[j])+1);
				}
			}
		}
		
		int ans = 0;
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				if(map.containsKey(-C[i]-D[j])) {
					ans += map.get(-C[i]-D[j]);
				}
			}
		}
		bw.write(ans+"");
		bw.close();
	}

}

시간초과 나오는 코드입니다

package baekjoon;

import java.util.*;
import java.io.*;

public class b7453 {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());
		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++) {
			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());
		}
		
		int AB[] = new int[n*n];
		int CD[] = new int[n*n];
		
		int idx = 0;
		for(int i = 0 ; i < n; i++) {
			for(int j = 0 ; j < n ; j++) {
				AB[idx] = A[i] + B[j];
				CD[idx++] = C[i] + D[j];
			}
		}
		Arrays.sort(AB);
		Arrays.sort(CD);
		
		long ans = 0;
		int left = 0;
		int right = n*n-1;

		while(left < n*n && right >= 0) {
			int tmp = AB[left] + CD[right];
			if(tmp < 0) {
				left++;
			} else if(tmp > 0) {
				right--;
			} else {
				long leftCnt = 1;
				long rightCnt = 1;
				while(left+1 < n*n && AB[left]==AB[left+1]) {
					left++;
					leftCnt++;
				}
				while(right-1 >= 0 && CD[right]==CD[right-1]) {
					right--;
					rightCnt++;
				}
				ans += leftCnt*rightCnt;
				right--;
			}
		}
		bw.write(ans+"");
		bw.close();
	}

}

이 문제 찾아보니까 풀이가 되게 다양하더라구요

백준 7453번: 합이 0인 네 정수 (JAVA) (tistory.com)

이 선생님 풀이 참고했는데 여기 들어가면 이진탐색으로 하는 풀이도 있어요

[python]백준 1208번 - 부분수열의 합 2 (tistory.com)

이거 저번에 비슷한 문제인데 파이썬 이진탐색 메소드 써서 풀었던 건데

자바도 찾아보니까 메소드가 있긴 하더라구요

Java의 이진 탐색(Binary Search) 메서드 사용하기 (Comparator 구현) :: 마음대로 개발 LIFE (tistory.com)

Java의 이진 탐색(Binary Search) 메서드 사용하기 (Comparator 구현)

Java의 기본 라이브러리에는 Binary Search 메서드가 내장되어 있습니다. java.util.Arrays 클래스에 존재합니다. 다양한 자료형의 배열을 사용할 수 있에 오버로딩되어 있는데, 본 아티클에서는, 제너릭

woojin.tistory.com

지금은 알바 가야하니까 자바 이진탐색 메소드는 다음기회에 알아보겠습니당~~

문제 풀때 최대 피해자 ㅠ 챗씨 ㅠ