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

문제

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

---

입력

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

---

출력

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

---

 

---

문제 접근 방법

이번 문제는 삽입과 동시에 정렬을 진행할 것인지, 혹은 입력을 다 받고 정렬을 할 것인지 두 가지를 비교해보도록 하겠다.

1. 삽입과 동시에 정렬 - PriorityQueue

우선순위 큐를 사용하여 오름차순으로 입력된 숫자를 큐에 삽임 함과 동시에 정렬이 되도록 코드를 짠다.

2. 삽입 후 정렬 - 1) int [] + Arrays.sort()

                       2) ArrayList + Collections.sort()

1차원 배열과 ArrayList로 입력을 배열에 삽입하고 모든 입력이 끝난 후 오름차순으로 배열을 정렬하여 출력한다.

---

JAVA 코드 풀이

1. 삽입과 동시에 정렬 - PriorityQueue

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());
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        while(num-- > 0)
            pQ.add(Integer.parseInt(br.readLine()));
        while(!pQ.isEmpty())
            bw.write(pQ.remove()+"\n");
        bw.close();
    }
}

2. 삽입 후 정렬 - 1) int [] + Arrays.sort()

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());
        int list[] = new int[num];
        for(int i=0; i<num; i++)
            list[i] = Integer.parseInt(br.readLine());
        Arrays.sort(list);
        for(int i=0; i<num; i++)
            bw.write(list[i]+"\n");
        bw.close();
    }
}

2. 삽입 후 정렬 - 2) ArrayList + Collections.sort()

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());
        ArrayList<Integer> aList = new ArrayList<>();
        while(num-- > 0)
            aList.add(Integer.parseInt(br.readLine()));
        Collections.sort(aList);
        for(int i=0; i<aList.size(); i++)
            bw.write(aList.get(i)+"\n");
        bw.close();
    }
}

코드 실행 결과

1. 삽입과 동시에 정렬 - PriorityQueue

2. 삽입 후 정렬 - 1) int[] + Arrays.sort()

2. 삽입 후 정렬 -  2) ArrayList + Collections.sort()

메모리 : ArrayList > PriorityQueue > int []

연산 속도(클수록 빠름) : int [] >  ArrayList > PriorityQueue

---

후기

이번 문제에서는 1차원 배열이 가장 성능이 좋게 나왔다. 확실히 입력되는 수의 개수가 정해져 있고, 배열의 개수 변동이 없으면 연산적인 측면에서는 1차원 배열이 가장 성능이 좋은 것 같다.

---

문제 원본

https://www.acmicpc.net/problem/2751