[백준][Java] 수 정렬하기 문제(2751번)

문제

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

풀이 코드

public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));   //Scanner 대신 BufferedReader로 썼다.
    StringBuilder sb = new StringBuilder();     //String대신 String Builder을 사용
    int n = Integer.parseInt(br.readLine());    //br.readLine()은 문자열로 입력되므로 parseInt를 사용
    List<Integer> list = new ArrayList<>();

    for (int i = 0; i < n; i++) {
        list.add(Integer.parseInt(br.readLine()));
    }

   Collections.sort(list);                      //시간이 오래 걸리는 Arrays.sort대신 Collections.sort사용

    for (int i : list) {
        sb.append(i).append("\n");              //sb에 한번에 저장한 뒤, 출력
    }
    System.out.println(sb);
}

이 문제는 시간 제한이 없거나 입력되는 숫자의 갯수가 적으면 풀기 쉽다.

그냥 입력 받고 Arrays.sort()를 이용하여 정렬하면 끝이다.

하지만 이렇게 풀게 되면 위 문제는 반드시 시간 제한에 걸려서 풀 수가 없다....(내가 그랬다ㅠ)

 

그래서 원래는 나도 Scanner를 이용한 입력방법과 출력할 때도 딱히 시간을 신경쓰지 않았는데 이번 일을 계기로 
출력에도 신경을 쓰기로 했고 Scanner보단 BufferedReader을 귀찮아도 많이 사용하기로 했다.

그리고 System.out.println대신에 BufferedWriter을 사용해서 더 시간을 줄일 수도 있지만
BufferedWriter을 사용하는 것보다 StringBuilder를 사용하는게 성능도 크게 차이가 없고 쓰는 입장에서도 덜 귀찮다!!!

 

주의할 점은 BufferedReader을 사용하여 입력받을 때, String형태로 입력을 받아서 Line단위로 읽기 때문에
공백을 구분해주고 싶으면 따로 split과 같은 함수를 이용해서 나눠줘야된다.

그리고 Arrays.sort보다 Collections.sort가 더 빠른데 그 이유는 서로의 정렬 방식이 달라서

Arrays.sort의 경우 시간복잡도가 평균 : O(nlog(n)) / 최악 : O(n^2)이고

Collections.sort의 경우 시간복잡도가 평균과 최악모두 O(nlog(n))라서

상황에 따라 맞는 것을 쓰면 되지만 최적의 시간으로 알고리즘을 풀고 싶으면 Collections.sort를 쓰는게 맞는 것 같다.