[PS] 백준 2751번 수 정렬하기 2

문제

2751번: 수 정렬하기 2

풀이

참고한 풀이

N(1 ≤ N ≤ 1,000,000) 라는 점 주의.

 

최악의 경우에도 O(nlogn) 을 보장하거나 혹은, O(n) 에 가까운 정렬 알고리즘을 사용해야 한다(Arrays.sort 로 쓰면 시간초과됨)

 

1. Collections.sort() 사용 : 병합(최악) + 삽입(최선) hybrid sorting algorithm. O(n) ~ O(nlogn) 을 보장

2. Counting sort  사용

 

1번 방법을 사용해보았다.정처기 준비하는 동안 자바를 다 까먹어서 큰일이다... 다시 공부해야겠다 ㅠㅜ

 

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

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

        int N = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<N; i++) {
            list.add(sc.nextInt());
        } //숫자값 넣음

        Collections.sort(list);

        for(int num : list) {
            sb.append(num).append("\n");
        }

        System.out.println(sb);
    }
}