백준 2751 수 정렬하기2 java 풀이

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

나의 풀이

 문제 자체는 간단하다. 주어지는 중복없는 자연수를 오름차순 정렬해서 출력해라. 그리고 문제 목록에서 nlogn의 연산이 필요하다고 간략하게 설명이 있다. 이를 보고 가장 먼저 떠오른건 역시 퀵정렬. 시간복잡도가 n^2 부터 nlogn, n까지 기본적이고 가장 많이 사용되는 알고리즘들에 대해 공부했었는데, 퀵정렬이 가장 기억에 남았었다. 그런데 퀵정렬이 가장 안좋은 상황에서 n^2의 시간복잡도로 동작한다는 것은 봤었긴 하지만 제대로 기억을 못하고 있었다. 자연스럽게 퀵정렬로 구성되어 있는 Arrays.sort() 함수를 이용하였으나 시간초과로 실패. 덕분에 정렬에 대해 다시 살펴볼 기회가 되었다... 문제 해결 방법은 Collections.sort() 기능인데, Collections.sort()는 반복합병&삽입 정렬로 구성되어 n부터 nlogn까지의 시간복잡도를 보장하였다. 이를 이용해 작성한 코드로는 테스트 통과.

 

 정렬에 대해 보고 정리해 보았다.

 

 

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<num; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        
        Collections.sort(list);
        
        Iterator<Integer> it = list.iterator();
        while(it.hasNext()) {
            bw.write(it.next()+"\n");
        }
        
        bw.flush();
    }
}