글 읽기 - java 시간초과 질문

yih9329 5년 전 0

최대로 줄인것 같은데 어떤 부분에서 시간초과가 나는거죠...?

도움을 주세요....

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main{
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			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++) {
				String[] s = br.readLine().split(" ");
				int a = Integer.parseInt(s[0]);
				int b = Integer.parseInt(s[1]);
				int c = Integer.parseInt(s[2]);
				int d = Integer.parseInt(s[3]);
				
				A[i] = a;	B[i] = b;	C[i] = c;	D[i] = d;
			}
			
			List<Integer> AB = new ArrayList<>();
			List<Integer> CD = new ArrayList<>();
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					AB.add(A[i] + B[j]);
					CD.add(C[i] + D[j]);
				}
			}
			
			Collections.sort(AB);
			Collections.sort(CD);
			int sum = 0;
			int cnt = 0;
			
			for(int i=0; i<AB.size(); i++) {
				if(i>0) {        // 이전과 같은 값을 찾는다면 탐색을 하지 않고 이전에 구한 값을 더해준다.
					if(AB.get(i) == AB.get(i-1)) {
						sum += cnt;
						continue;
					}
				}
				
				int val = 0 - AB.get(i);
				int left = 0;
				int right = CD.size()-1;
				cnt = 0;
				
				while(left<=right) {
					int mid = (left + right) / 2;
					
					if(CD.get(mid) > val) {
						right = mid - 1;
					}
					
					else if(CD.get(mid) < val) {
						left = mid + 1;
					}
					
					else {                            // 해당하는 값을 찾았다면 그 값 주위로 같은 값이 있는지 확인.
						cnt++;
						for(int j=mid-1; j>=0 ;j--) {
							if(CD.get(j) != val)
								break;
							cnt++;
						}
						
						for(int j=mid+1; j<CD.size(); j++) {
							if(CD.get(j) != val)
								break;
							cnt++;
						}
						sum += cnt;
						break;
					}
				}
			}
			
			bw.write(Integer.toString(sum));
			bw.close();
			br.close();
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
	
}

djm03178 5년 전 1

71번째 줄처럼 주위로 같은 값들을 반복문으로 찾아나가게 되면 최악의 경우 O(N^4)이 됩니다. 가장 쉽게 생각할 수 있는 케이스로 배열의 모든 원소가 0인 경우를 생각해보시면 됩니다.

이 문제에서 이분 탐색을 활용하려면 lower bound와 upper bound를 이용해서 저런 반복문 없이 두 번의 이분 탐색으로 처리할 수 있어야 합니다.

yih9329 5년 전 0

답변 감사드립니다

말씀하신대로 구현했는데 이전코드와 똑같은 부분에서 시간초과가 난다고 뜨네요..

구현상에 잘못된 것이 있을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main{
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			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++) {
				String[] s = br.readLine().split(" ");
				int a = Integer.parseInt(s[0]);
				int b = Integer.parseInt(s[1]);
				int c = Integer.parseInt(s[2]);
				int d = Integer.parseInt(s[3]);
				
				A[i] = a;	B[i] = b;	C[i] = c;	D[i] = d;
			}
			
			List<Integer> AB = new ArrayList<>();
			List<Integer> CD = new ArrayList<>();
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					AB.add(A[i] + B[j]);
					CD.add(C[i] + D[j]);
				}
			}
			
			Collections.sort(AB);
			Collections.sort(CD);
			int sum = 0;
			int lower_bound = 0;
			int upper_bound = 0;
			
			for(int i=0; i<AB.size(); i++) {
				if(i>0) {
					if(AB.get(i) == AB.get(i-1)) {
						sum += upper_bound - lower_bound;
						continue;
					}
				}
				
				int val = 0 - AB.get(i);
				int left = 0;
				int right = CD.size()-1;
				int mid = 0;
				lower_bound = 0;
				upper_bound = 0;
				int check = 0;
				
				while(left<right) {
					mid = (left + right) / 2;
					
					if(CD.get(mid) >= val) {
						if(CD.get(mid) == val)
							check = 1;
						right = mid;
					}
					
					else {
						left = mid + 1;
					}
					
				}
				
				if(check == 1) {
					lower_bound = right;				
					left = 0;
					right = CD.size()-1;
	
					while(left<right) {
						mid = (left + right) / 2;
						
						if(CD.get(mid) > val) {
							right = mid;
						}
						
						else {
							left = mid + 1;
						}	
					}
					
					if(right == CD.size()-1 && CD.get(CD.size()-1) == val)
						upper_bound = right + 1;
					
					else
						upper_bound = right;
				}
				
				sum += upper_bound - lower_bound;
			}
			
			bw.write(Integer.toString(sum));
			bw.close();
			br.close();
		} catch(IOException e) {
			e.printStackTrace();
		}
	}
	
}

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

문제

문제

출처

ICPC

java 시간초과 질문

yih9329 5년 전 0

djm03178 5년 전 1

yih9329 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말