큰 배열을 조작 할 때 성능을 향상시키는 방법은 무엇입니까?

Question

지금 Hackerrank에서 문제를 해결하고 있으며 논리가 다소 정확하다고 믿지만 큰 데이터 세트는 성능이 저하되어 "잘못된"답변을 얻습니다. 당신이 그것을 확인할 수 있도록 여기에 문제에 대한 링크는 다음과 같습니다

https://www.hackerrank.com/challenges/qheap1

내가 큰 데이터 세트를 허용하기 위해이 스크립트의 성능을 향상하는 방법을 궁금해하고있다. 나는 스캐너와 관련이 있다는 직감이 있지만 그 이유는 모르겠다.

public class Solution { 
    private static final int ADD = 1; 
    private static final int DELETE = 2; 
    private static final int GET = 3; 
    private static final int TICK = 1; 
    public static void main(String[] args) { 
     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
     Scanner in = new Scanner(System.in); 
     PrintStream out = System.out; 
     int n = in.nextInt(); 
     int[] heap = new int[n]; 

     int a = 0; 
     while (a < n) { 
      a = 0; 
      int q = in.nextInt(); 

      switch(q) { 
       case(ADD): 
        int nextAdd = in.nextInt(); 
        /*out.println("ADD " + next);*/ 
        int b = 0; 
        while (b < n) { 
         /*out.println(heap[b]);*/ 
         if (heap[b] == 0) { 
          heap[b] = nextAdd+TICK; 
          /*printArray(heap);*/ 
          b = n-1; 
         } 
         b++; 
        } 
        /*printArray(heap);*/ 
        break; 
       case(DELETE): 
        int c = 0; 
        int nextDelete = in.nextInt(); 
        while (c < n) { 
         if (heap[c]-TICK == nextDelete) { 
          heap[c] = 0; 
          c = n-1; 
         } 
         c++; 
        } 
        /*printArray(heap);*/ 
        break; 
       case(GET): 
        Arrays.sort(heap); 
        int d = 0; 
        while (d < n) { 
         if (heap[d] != 0) { 
          out.println(heap[d]-TICK); 
          d = n-1; 
         } 
         d++; 
        } 
        /*printArray(heap);*/ 
        break; 
      } 
      a++; 
      /*printArray(heap);*/ 
     } 
    } 

    public static void printArray(int[] ar) { 
     String str = ""; 
     for (int i : ar) { 
      str += i + " "; 
     } 
     System.out.println(str); 
    } 
} 

Answer 1

코드를 보면, 내가 발견 할 수있는 유일한 즉시 문제는이 라인

out.println(heap[d]-TICK); 

이 주석되지 않는다는 사실이다. 그건 당신의 자바 프로그램 (아니, 스크립트, 당신의 말을 염두에 두지 마라.) 많은 IO 작업을하고있다. 그리고 그들은 매우 비싼 다른 어떤 프로그램에 비해.

그래서 댓글을 달아서 어떻게되는지 확인하십시오.

Answer 2

힙을 사용하지 않는 (챌린지에서 요구하는 것처럼) 힙을 사용하지 않는 주된 문제점은 배열 작업에 너무 많은 시간을 소비하고 있다는 것입니다.

public static void main(String[] args) { 
    final Scanner in = new Scanner(System.in); 

    final int n = in.nextInt(); 
    final PriorityQueue<Integer> q = new PriorityQueue<>(n); 
    for (int i = 0; i < n; i++) { 
     final int command = in.nextInt(); 
     switch (command) { 
     case 1: 
      q.add(in.nextInt()); 
      break; 
     case 2: 
      q.remove(in.nextInt()); 
      break; 
     case 3: 
      System.out.println(q.peek()); 
      break; 
     } 
    } 
}