[백준] 2751 수 정렬하기 2, java

2751번: 수 정렬하기 2

백준의 실버5 문제입니다. 이전에 풀었던 2750문제와 내용은 같지만 입력에 주어질 수 있는 수의 범위가 많이 증가했습니다. 그렇기 때문에 이전의 코드로 시도를 해봤지만 시간초과가 나타나게 됩니다.

 

import java.util.*;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++){
            arr[i] = sc.nextInt();
        }
        
        Arrays.sort(arr);
        
        for(int i=0; i<n; i++){
            System.out.println(arr[i]);
        }
    }
}

시간초과

그래서 Scanner 보다 입력받는 시간을 줄일 수 있는 BufferedReader를 이용한 입력을 받은 뒤 시도를 해보았는데 이 역시도 시간초과가 나타나게 됩니다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception{
    	//입력을 Scanner에서 BufferedReader로 변경
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arr);
        
        for(int i=0; i<n; i++){
            System.out.println(arr[i]);
        }
    }
}

시간초과

 

이제 입력은 물론 출력도 더 빠른 방법을 찾아보아야 합니다. 출력으로는 매번 System.out.println()을 사용하는 것이 아니라 한 번에 완성된 문자열을 보낼 수 있도록 StringBuilder를 사용해 보았습니다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arr);
        
        //StringBuilder를 통해서 한번에 출력할 수있는 문자를 만듭니다.
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<n; i++){
            sb.append(arr[i] +"\n");
        }
        
        System.out.println(sb.toString().trim());
    }
}

성공

데이터의 양에 따라서 입력, 출력의 방식에 따른 시간소요가 많이 달라질 수 있음을 알게 해주는 문제였습니다.

 

이상입니다!