[백준] 2751 - 수 정렬하기 2 (JAVA/ 자바)

2751번 문제

이전의 수 정렬하기 문제와 똑같길래 그 때 사용한 코드를 한 번 제출했더니 역시나... 시간 초과가 떴다.

이것저것 코드를 수정해가면서 했는데도 여전히 시간 초과가 뜨길래 다짜고짜 "Arrays.sort()보다 빠른 방법"이라고 검색해봤다.

 

그랬더니 발견한 Collections.sort().

Arrays.sort()는 Quick Sort(퀵 정렬) 방식을 사용하고,

Collections.sort() 는 Insertion Sort(삽입 정렬)과 Merge Sort(병합 정렬)이 합쳐진 Tim Sort 를 사용한다.

https://d2.naver.com/helloworld/0315536

 

Collections.sort()로 정렬을 하려면 List로 받아와야한다.

처음에 Scanner로 받아오려고 했는데 시간초과가 나서 Scanner보다 빠른 BufferedReader만 사용하였다.

List로 받아서 출력하게 되면 [1,2,3,4,5] 이런 식으로 출력이 되게 되는데,

https://adjh54.tistory.com/129

[Java] String, StringBuffer, StringBuilder 이해하기

이 분의 글을 참고하여 StringBuilder를 이용해 한 줄씩 출력되게 하였다.

 

BufferedReader를 이용한 방법

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

public class Main{
public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
   
    int N = Integer.parseInt(br.readLine());
    List<Integer> list = new ArrayList<>();
    
    for(int i=0; i<N; i++){
        list.add(Integer.parseInt(br.readLine()));
    }
    Collections.sort(list);
    for(int i: list){
        sb.append(i).append("\n");
    }
    System.out.println(sb);
    br.close();
    }
}

알고리즘은 언제나 어려운 것 같다... 많은 공부가 필요하다...