[백준/JAVA] 2751: 수 정렬하기2

[백준/JAVA] 2751: 수 정렬하기2

n개의 수를 오름차순으로 정렬하는 문제이다. n의 개수와 그 절댓값의 크기가 상당히 넓어서 처음에 아무 생각 없이 sort를 썼다가 시간 초과가 났다.

시간복잡도를 줄이기 위해서 다음 방법들을 사용했다.

• Scanner 대신 BufferedReader 사용하기
• println 대신 BufferedWriter 사용하기
• Arrays.sort 대신 Collections.sort 사용하기

아래 코드로 1616ms가 나왔는데 시간을 더 줄일 방법이 있을 것이다. 이것에 대해 더 고민해봐야겠다.

소스코드

---

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

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
    	int n = Integer.parseInt(br.readLine());
    	ArrayList<Integer> set = new ArrayList<>();
    	
    	for(int i=0; i<n; i++)
    		set.add(Integer.parseInt(br.readLine()));
    	
    	Collections.sort(set);
    	
    	BufferedWriter bw = 
    			new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	for(int i: set)
    		bw.write(i+"\n");
    	bw.flush();
    }
}