100000 개의 인풋을 받는데서 타임아웃이 걸리는 건지
아니면 알고리즘상 문제가 있는 건지 잘 모르겠네요
배열로 비교했는데도
타임아웃이 나서 어떻게 손을 댈지 막막합니다
java 사용자 분들께 도움을 부탁드립니다
importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intcases=sc.nextInt();double[]arrX,arrY;arrX=newdouble[100000];arrY=newdouble[100000];intarrLen=0;while(cases-->0){intN;longresult=0;doublep,q;N=sc.nextInt();p=sc.nextDouble();q=sc.nextDouble();while(N-->0){arrX[arrLen]=sc.nextDouble();arrY[arrLen]=sc.nextDouble();arrLen++;}for(inti=0;i<arrLen;i++){for(intj=i+1;j<arrLen;j++){if(func(arrX[i],arrY[i],arrX[j],arrY[j],p)^func(arrX[i],arrY[i],arrX[j],arrY[j],q))result++;}}System.out.println(result);}sc.close();}//A가 B보다 왼쪽인가? 에 대한 Booleanpublicstaticbooleanfunc(doubleax,doubleay,doublebx,doubleby,doublep){if(ax==p||bx==p){if(ax<bx)returntrue;elsereturnfalse;}elseif(ay/(ax-p)>by/(bx-p))returntrue;elsereturnfalse;}}
이 문제에서 주어지는 N이 최대 100,000인데, 시간복잡도가 O(N^2)인 모든 쌍을 비교하는 알고리즘으로 구현하시는 경우 시간초과가 나게 됩니다. 연산의 종류에 따라 다르긴 하지만, 보통 1억 ~ 3억번의 연산을 하는 경우 1초 정도의 시간이 걸릴 것이라 예상하시고 구현하시면 됩니다.
changheum
100000 개의 인풋을 받는데서 타임아웃이 걸리는 건지
아니면 알고리즘상 문제가 있는 건지 잘 모르겠네요
배열로 비교했는데도
타임아웃이 나서 어떻게 손을 댈지 막막합니다
java 사용자 분들께 도움을 부탁드립니다
7년 전