2751 JAVA 수 정렬하기 2

2751번: 수 정렬하기 2

🍀 문제

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

🍀 입력

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

🍀 출력

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

🍀 예제 입력 1

5
5
4
3
2
1

🍀 예제 출력 1

1
2
3
4
5

🍀 코드 과정

틀린 코드 1

처음에 HashMap 을 사용하려고했다. 자동으로 정렬이 되는 줄 알고 있었는데, HashMap이 아니라 Heap 이 자동정렬을 지원하는 것이었다. 자바는 Heap을 내장하고 있지 않기 때문에 다른 방법을 이용하고자 했다.

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        // 입력
        HashMap<Integer, Integer> sMap = new HashMap<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n ; i ++){
            sMap.put(Integer.parseInt(br.readLine()), 0);
        }

        //출력
        for (int key : sMap.keySet()){
            System.out.println(key);
        }
    }
}

틀린코드 2

ArrayList를 이용했다. 내장 함수인 ArrayList.sort()는 최소 O(nlongN)을 지원하지만 악의 경우 O(N^2)를 지원하기 때문에 O(N^2)이 되지 않는 이 문제에서는 사용이 불가능하다. 따라서, Collections.sort()를 이용하여 문제를 해결하였다.

현재 문제는 2초의 시간 제한이 있으므로 총 2억번의 연산만 수행이 가능하다.
하지만, 현재 N의 값은 10^6 이므로 2초동안의 시간동안 O(N^2)일 경우 10^12번의 연산을 진행한다. 따라서, O(N)에 가깝게 접근해야하는 것이다.

틀린코드 3

그럼에도 불구하고 시간초과가 났다. 그 이유는 System.out.println이 StringBuilder 에 비해 시간소요량이 높은 것이었다. 따라서 변경 후 최종 코드는 다음과 같다.

최종 코드

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        // 입력
        ArrayList<Integer> sArray = new ArrayList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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

        Collections.sort(sArray);
        
        StringBuilder sb = new StringBuilder();
        //출력
        for (int value : sArray){
            sb.append(value).append('\n');
        }
        System.out.println(sb);
    }
}