풀 카운트 정렬 속도를 높일 방법

Question

hackerrank에서 질문이 생겼습니다. https://www.hackerrank.com/challenges/countingsort4

첫 번째 시도는 시간 초과로 인해 마지막 테스트 케이스를 제외한 모든 테스트 케이스를 통과했습니다. 보다 효율적인 알고리즘을 찾지 못한 후에 String을 직접 연결하는 대신 StringBuilder를 사용하여 코드를 개선했습니다. 이것은 5 초 이상에서 3.5 초로 작동 시간을 가져 왔습니다.

내 질문에 내가 달리기 시간을 향상시킬 수있는 다른 방법이 있습니까? 감사합니다. .

다음은 제 코드입니다.

public class Solution { 

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

     int N = scanner.nextInt(); 
     scanner.nextLine(); 

     int[] oriNum = new int[N];   
     String[] oriStr = new String[N]; 
     int[] count = new int[100]; 
     int[] indices = new int[100]; 
     int[] output = new int[N]; 

     // save the originals and the count array 
     for (int i = 0; i < N; i++) { 
      oriNum[i] = scanner.nextInt(); 
      oriStr[i] = scanner.nextLine().trim(); 
      count[oriNum[i]]++; 
     } 

     // accumulate the count array 
     indices[0] = 0; 
     for (int i = 1; i < 100; i++) { 
      indices[i] = indices[i-1] + count[i-1]; 
     } 

     // output order 
     for (int i = 0; i < N; i++) { 
      int num = oriNum[i]; 
      output[indices[num]++] = i; 
     } 

     int bar = N/2; 
     StringBuilder sb = new StringBuilder(); 
     for (int i = 0; i < N; i++) {    
      int index = output[i]; 
      if (index < bar) 
       sb.append("- "); 
      else 
       sb.append(oriStr[index]+ " "); 
     } 
     System.out.println(sb.toString()); 
    } 
} 

Answer 1

스캐너 대신 일반 버퍼링 된 리더를 사용해보십시오. 스캐너가 놀라 울 정도로 느리고 스캐너가 "제한 시간 초과"의 유일한 이유 인 프로그래밍 경연 대회에 참가했습니다.

Answer 2

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 
public class Solution 
{ 
    public static void main(String[] args)throws Exception 
{ 
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in)); 
    int n=Integer.parseInt(in.readLine()); 
    int[] c=new int[100]; 
    String[][] dt=new String[100][10300]; 
    for(int i=0;i<n;i++) 
    { 
     String[] str=in.readLine().split(" "); 
     int val=Integer.parseInt(str[0]); 
     if(i<n/2) 
      dt[val][c[val]]="-"; 
     else 
      dt[val][c[val]]=str[1]; 
     c[val]++; 
    } 
    StringBuilder sb=new StringBuilder(""); 
    for(int i=0;i<100;i++) 
     if(i<n) 
     for(int k=0;k<c[i];k++) 
      if(dt[i][k]!=null) 
       sb.append(dt[i][k]+" "); 
      else break; 
    System.out.println(sb.toString()); 
} 
}