백준 2751 수 정렬하기 2

2751번: 수 정렬하기 2

 

2750번이랑 조건도 같아서 ?? 그냥 쓰면 되는건가? 했는데...

 

1. Scanner + arrays.sort --> 시간 초과❌

import java.util.Scanner;
import java.util.Arrays;

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

        int len=sc.nextInt();

        int[] arr=new int[len];

        for(int i=0; i<arr.length; i++){
            arr[i]=sc.nextInt();
        }

        Arrays.sort(arr);

        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }
    }
}​

 

Scanner보단 BufferedReader가 훨씬 빨라서 바꾸고 ArrayList로 바꿔서 했는데

2. BufferedReader + ArrayList --> 시간초과❌

아무래도 출력할때 시간이 또 오래 걸려서 그런듯

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<>();

        int num = Integer.parseInt(br.readLine());

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

        Collections.sort(list);

        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }
    }
}

 

결국 구글링해서 찾아보니 출력할 때 배열 원소 하나씩 출력하면 시간 초과 발생한다

그래서 StringBuider 사용해서 한번에 출력해줘야 한단다.

3. BufferedReader + ArrayList를 StringBuilder에 넣어놓고 StringBuilder를 이용해 한번에 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<Integer>();
        StringBuilder sb = new StringBuilder();

        
        int num = Integer.parseInt(br.readLine());

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

        Collections.sort(list);

        for(Integer i:list){
            sb.append(i).append('\n');
        }
        System.out.println(sb);
    }
}

Scanner <> BufferedReader도 중요하긴 하지만 이 문제에서 가장 중요한 건 정렬 알고리즘과 출력 방법인듯

Arrays.sort()의 경우에는 dual-pivot quicksort 알고리즘을 사용하는데 평균 시간 복잡도가 o(nlogn)이지만 최악의 시나리오에는 o(n^2)이기 때문에 시간 초과가 날수 있음

그래서 반복합병 및 삽입 알고리즘을 사용하는 Collections.sort()를 이용해야 한다. 해당 알고리즘은 시간복잡도 o(n) ~ o(nlogn)를 보장함

 

그리고 다음으로 주의할점이 출력할때 한번에 모두 출력해줘야 함

StringBuider를 이용해서 한번에 출력. >>StringBuider와 StringBuffer 공부하기