ANNIETIBBER 문제 JAVA에서 타임아웃이 납니다...

  • changheum
    changheum

    100000 개의 인풋을 받는데서 타임아웃이 걸리는 건지
    아니면 알고리즘상 문제가 있는 건지 잘 모르겠네요

    배열로 비교했는데도
    타임아웃이 나서 어떻게 손을 댈지 막막합니다

    java 사용자 분들께 도움을 부탁드립니다

    import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int cases = sc.nextInt();
            double [] arrX, arrY;
            arrX = new double[100000];
            arrY = new double[100000];
            int arrLen = 0;
    
            while(cases-- > 0) {
                int N;
                long result = 0;
                double p, q;
    
                N= sc.nextInt();
                p= sc.nextDouble();
                q= sc.nextDouble();
    
                while(N-- > 0) {
                    arrX[arrLen] = sc.nextDouble();
                    arrY[arrLen] = sc.nextDouble();
                    arrLen++;
                }
                for( int i= 0; i< arrLen; i++){
                    for(int j=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보다 왼쪽인가? 에 대한 Boolean
        public static boolean func(double ax, double ay, double bx, double by, double p)
        {
            if( ax == p || bx == p ){
                if( ax < bx) return true;
                else return false;
            }
            else if( ay/(ax-p) > by/(bx-p))
                return true;
            else
                return false;
        }
    }
    

    7년 전
2개의 댓글이 있습니다.
  • Corea
    Corea

    이 문제에서 주어지는 N이 최대 100,000인데, 시간복잡도가 O(N^2)인 모든 쌍을 비교하는 알고리즘으로 구현하시는 경우 시간초과가 나게 됩니다. 연산의 종류에 따라 다르긴 하지만, 보통 1억 ~ 3억번의 연산을 하는 경우 1초 정도의 시간이 걸릴 것이라 예상하시고 구현하시면 됩니다.


    7년 전 link
  • changheum
    changheum

    조언 감사드립니다^^


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.