[백준_2751] 수 정렬하기 2 - JAVA

문제출처

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

풀이

• 간단한 Sort 문제이다.
  그러나 풀게되면 시간초과로 실패한다. 데이터가 10^6이므로 N^2 Sort가 아닌 nlogn의 Sort 알고리즘을 사용해야한다.
  선택/삽입/버블의 경우 N^2 이므로 다른 Sort인 퀵소트로 풀었는데 시간초과가 났다.
  퀵소트도 Worst Case의 경우 N^2이라고 함
  
  
• 풀이 접근
  1. Arrays.sort() -> 시간 초과 (최악의 경우 N^2)
  2. Collections.sort() -> 시간 초과 (1 보다 캐시 참조 지역성이 좋음)
  3. 출력 sout에 문제가 있는 것 같아 BufferedWriter로 변경하여 해결 완료

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            list.add(Integer.parseInt(stringTokenizer.nextToken()));
        }
        Collections.sort(list);
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out)); // 선언
        for (int i = 0; i < N; i++) {
            bufferedWriter.write(String.valueOf(list.get(i)) + "\n");
        }
        bufferedReader.close();
        bufferedWriter.flush();
        bufferedWriter.close();
    }
}

채점 결과