글 읽기 - 자바 7453번 시간초과

qkrxorb10 6년 전 0

A,B 합을 AB

C,D 합을 CD 리스트에 저장하여, 정렬 후 이분탐색을 했는데 시간초과가 나네요.

이유를 알 수 있을까요...

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int result = 0;
	public static void binarySearch(int num, int first, int last, List<Integer> list) {
		
		if(first < last) {
			int mid = (first + last) / 2; 
			if(-num < list.get(mid)) {
				binarySearch(num, first, mid, list);
			}else if(-num > list.get(mid)){
				binarySearch(num, mid+1, last, list);
			}else {
				result++;
				return;
			}
		}
		
		
	}

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Integer> A = new ArrayList<>();
		List<Integer> B = new ArrayList<>();
		List<Integer> C = new ArrayList<>();
		List<Integer> D = new ArrayList<>();
		
		List<Integer> AB = new ArrayList<>();
		List<Integer> CD = new ArrayList<>();
		
		for(int i=0; i<n; i++) {
			A.add(sc.nextInt());
			B.add(sc.nextInt());
			C.add(sc.nextInt());
			D.add(sc.nextInt());
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				AB.add(A.get(i) + B.get(j));
				CD.add(C.get(i) + D.get(j));
			}
		}
		
		Collections.sort(AB);
		Collections.sort(CD);
		
		for(int i=0; i<AB.size(); i++) {
			binarySearch(AB.get(i), 0, CD.size(), CD);
		}
		
		System.out.println(result);
		
	}

}

bok03220 4년 전 0

정렬을 2번하면 시간초과가 날 겁니다..

1번 돌리는 것도 아슬아슬하다고 생각합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

자바 7453번 시간초과

qkrxorb10 6년 전 0

bok03220 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말