글 읽기 - 계속 시간초과가 나오는데 이유를 모르겠네요...

koola97620 7년 전 0

이전 문제도 계속 시간초과로 실패했었는데 이 문제도 실패가 떠서...

그냥 지나가기엔 답답해서 처음으로 질문 올려봅니다 ㅠㅠ

우선 시간초과 의심 부분이 69,95번째 줄에서 시작하는 코드들 입니다.

69번째 줄의 while문은 점들을 입력받고 중복된 점이 있는지 검사를 한 후에

List에 넣는 코드들입니다. Scanner사용 보다는 이 방법이 더 빠를 거 같아서 이렇게 짰습니다.

95번째 줄은 점들을 하나씩 비교하는 이중 for문인데... 느낌으로는 이 부분이 시간초과의 원인인것

같기는 한데. 다른분들의 의견이 궁금해서 질문올려봅니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/* 가장 가가운 두 점의 거리.  < 5620번 >
 * 평면상에 n개의 점이 놓여져 있다고 할때, 거리가 최소인 두개의 점을 구하고 그 거리를 알고 싶다.
 * 가장 가까운 두 점 사이의 거리의 제곱을 출력하시오.
 * */


class Point {
	private int x;
	private int y;
	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
	
	@Override
	public int hashCode() {
		return this.x + this.y;
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj instanceof Point) {
			Point p = (Point)obj;
			if(this.x==p.x && this.y == p.y) {
				return true;
			}
		}
		return false;
	}
		
	
	
	
}

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
//		long startTime = System.nanoTime();
		
		int countPoint = Integer.parseInt(br.readLine().trim());
		if(countPoint > 100000000 || countPoint < 2) {
			return;
		}
		
		List<Point> points = new ArrayList<Point>();
		
		
		while(points.size() != countPoint) {
			String input = br.readLine().trim();
			String inputs[] = input.split(" ");
			
			// inputs[0] = x 좌표. inputs[1] = y 좌표.
			
			if(Integer.parseInt(inputs[0]) > 10000 || Integer.parseInt(inputs[0]) < -10000 ||  Integer.parseInt(inputs[1]) > 10000 || Integer.parseInt(inputs[1]) < -10000) {
				return;
			}
			
			
			Point temp = new Point(Integer.parseInt(inputs[0]), Integer.parseInt(inputs[1]));
			if(points.contains(temp)) {
				System.out.println("좌표중복");
				return;
			} else {
				points.add(temp);
			}
			
		}
		
//		for(Point p : points) {
//			System.out.println("x : " + p.getX() + " y : " + p.getY());
//		}
		
		int min=Integer.MAX_VALUE;
		for(int i=0 ; i < points.size()-1 ; i++) {
			for(int j=i+1 ; j < points.size() ; j++) {
				int dist = distance(points.get(i), points.get(j));
				if(dist < min) {
					min = dist;
				}
			}
			
		}
		System.out.println(min);
//		long endTime = System.nanoTime();
//		System.out.println("시간 :" + (endTime - startTime));//9379724493
		//5269129556

	}
	
	public static int distance(Point p1, Point p2) {
		int disX = Math.abs(p2.getX() - p1.getX());
		int disY = Math.abs(p2.getY() - p1.getY());
		
		return ((disX*disX) + (disY*disY));
	}

}

unused 7년 전 1

작성하신 코드대로라면 루프를 총 1억의 제곱 번 돌게 됩니다. 보통 루프 1억~2억 번 정도 도는 데 1초가 걸리므로, 작성하신 코드는 약 1억 초가 걸리겠네요. 시간제한이 1초인 문제이므로 당연히 시간 초과가 납니다.

이 문제를 푸는 데는 모든 쌍을 다 검사하는 것이 아닌, 더 효율적인 알고리즘이 필요합니다.

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

문제

문제

출처

ICPC

계속 시간초과가 나오는데 이유를 모르겠네요...

koola97620 7년 전 0

unused 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말