글 읽기 - [java]union_find와 ccw알고리즘으로 짜봤는데 시간초과입니다 ..

isvara 4년 전 0

입출력부분에서 시간이 나올리는 없을거같은데 4%부근까지가서 그냥 시간초과가 뜹니다.

N^2이면 9백만이면 이렇게 까지 막힐거같지는않는데 어디부분에서
시간을 잡아먹는걸까요 ??고수님들 지적부탁드립니다.

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


public class Main {
	public static boolean CCW(Line l1, Line l2){
		
		int clock1=(l1.x1*l1.y2 + l1.x2*l2.y1 + l2.x1*l1.y1) -
			(l1.x2*l1.y1 + l2.x1*l1.y2 + l1.x1*l2.y1);
		
		int clock2=(l1.x1*l1.y2 + l1.x2*l2.y2 + l2.x2*l1.y1) -
				(l1.x2*l1.y1 + l2.x2*l1.y2 + l1.x1*l2.y2);
		
		if(clock1 * clock2 <= 0)
			return true;
		
		int clock3=(l2.x1*l2.y2 + l2.x2*l1.y2 + l1.x2*l2.y1)-
				(l2.x2*l2.y1 +l1.x2*l2.y2 +l2.x1*l1.y2);
		
		int clock4=(l2.x1*l2.y2 + l2.x2*l1.y1 + l1.x1*l2.y1)-
				(l2.x2*l2.y1 +l1.x1*l2.y2 +l2.x1*l1.y1);
		
		if(clock3 * clock4 <=0)
			return true;
		
		return false;
	}
	public static void main(String[] args) throws IOException {
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		int N=Integer.parseInt(br.readLine());
		
		//초기화
		int ans=0;
		int[] chk=new int[N];
		Line[] Total=new Line[N];
		disjoinset Group=new disjoinset(N);
		
		for(int i=0; i<N; i++)
		{
			int x1,y1,x2,y2;
			String s;
			s=br.readLine();
			
			x1=(int)s.charAt(0);
			y1=(int)s.charAt(1);
			x2=(int)s.charAt(2);
			y2=(int)s.charAt(3);
			Total[i]=new Line(x1,y1,x2,y2);
		}
	
		for(int i=0; i<N; i++)
		{
			for(int j=i+1; j<N; j++)
			{
				if(CCW(Total[i],Total[j]))
				{
					if(Group.find(i) != Group.find(j))
						Group.merge(i, j);
				}
			}
		}
		
		for(int i=0; i<N; i++)
			{
				chk[Group.Parent.get(i)]++;
				if(Group.Parent.get(i)==i)
					ans++;
			}
		
		int res=0;
		for(int i=0; i<N; i++)
			res=Math.max(res, chk[i]);
		
		System.out.println(ans);
		System.out.print(res);
	}

}
class Line{
	int x1;
	int y1;
	int x2;
	int y2;
	
	public Line(int x1,int y1,int x2, int y2) {
		this.x1=x1;
		this.y1=y1;
		this.x2=x2;
		this.y2=y2;
	}
}
class disjoinset{
	ArrayList<Integer> Parent;
	disjoinset(int n){
		Parent=new ArrayList<Integer>(n);
		for(int i=0; i<n; i++)
		{
			Parent.add(i);
		}
	}

	public int find(int u){
		if(u==Parent.indexOf(u))
			return u;
		
		return find(Parent.indexOf(u));
	}
	public void merge(int u, int v) {
		if(Parent.indexOf(u)==Parent.indexOf(v))
			return;
		Parent.set(u, v);
	}
}

exponential_e 4년 전 0

이문제인지 모르겠지만 일단 48-51번째 줄에서 입력 잘못받고계십니다.

공백이 들어오기때문에 split 또는 StringTokenizer시사용해서 잘라주시고 int x1 = str.charAt(?) - '0'; 이렇게 받아주셔야 올바른 정수값으로 입력됩니다!

지금 질문자님 코드는 공백을 입력받고 있습니다..

isvara 4년 전 1

아... 감사합니다 공백부분을 신경을 못썻군요 그런데 고쳐도 시간초과가 뜹니다..

   x1=(int)s.charAt(0)-'0';
   y1=(int)s.charAt(2)-'0';
   x2=(int)s.charAt(4)-'0';
   y2=(int)s.charAt(6)-'0';

djm03178 4년 전 1

그리고 시간 초과의 원인은 disjointset이 매우 비효율적으로 구현되었기 때문입니다. 지금처럼 아무런 최적화 기법이 없는 구현은 매 호출 시마다 최악의 경우 O(N)의 시간이 걸립니다.

심지어 더 있습니다. ArrayList.indexOf는 최악의 경우 리스트 전체를 순회해야 하는 메서드로 이 호출 자체가 O(N)입니다. 전체 코드는 그래서 O(N^4)이 됩니다. 애초에 지금의 find 함수는 u의 부모를 찾는 것이 아니고 u를 부모로 가지는 원소(즉, u의 자식 중 하나)를 찾는 것이므로 아예 틀린 구현인 것 같습니다. get 메서드를 사용해야 합니다.

Path compression이나 rank를 사용해서 시간복잡도를 단축해야 합니다.

exponential_e 4년 전 0

아 죄송합니다 제가 문제를 제대로 안읽어봤네요 djm님 말씀이 맞고 입력을 공백기준쪼갠 것을 parse로 형변환해주시면 됩니다..

알맞는 형변환 관련해서도 몇개 찾아보시는 것을 추천드려요!

isvara 4년 전 0

아.. indexOf가 내부적으로 어떻게 작동하는지를 몰랐었네요 우선 전부배열로 고쳤습니다

그리고 알고리즘이 잘못된 부분이 방향만따지면 잘못된 예시가 나오는것같습니다.
거리도 따졌어야했던거같습니다. 감사합니다.

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

문제

문제

출처

ICPC

[java]union_find와 ccw알고리즘으로 짜봤는데 시간초과입니다 ..

isvara 4년 전 0

exponential_e 4년 전 0

isvara 4년 전 1

djm03178 4년 전 1

djm03178 4년 전 1

exponential_e 4년 전 0

isvara 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말