[JAVA / 자바] 백준 10989번 - 수 정렬하기 3

문제

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

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

---

출력

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

---

 

---

문제 접근 방법

카운팅 정렬을 사용하면 된다.

1. 입력으로 들어올 수 있는 수의 범위만큼 1차원 배열을 선언해준다.

2. 각각의 인덱스에 해당하는 숫자가 입력되면 해당 인덱스의 수를 +1 해준다.

3. 모든 인덱스를 순환하여 (인덱스 오름차순으로 순환) 배열에 저장된 수만큼 출력을 반복해주고 다음 인덱스로 넘어간다.

 

 

+)

아래 두 가지의 방법으로 작성한 코드도 결과를 비교해보겠다.

  1차원 배열(int []) + Arrays.sort()

  ArrayList <Integer> + Collections.sort()

---

JAVA 코드 풀이

 - 카운팅 정렬(Counting Sort)

 - 1차원 배열(int []) + Arrays.sort()

 - ArrayList <Integer> + Collections.sort()

코드 실행 결과

카운팅 정렬(Counting Sort) 코드 실행 결과

1차원 배열(int[]) + Arrays.sort() 코드 실행 결과

ArrayList<Integer> + Collections.sort() 코드 실행 결과

---

후기

처음에 나는 오름차순으로 정렬하여 풀라기에 당연히 받은 모든 수를 배열에 저장해 두고 오름차순으로 정렬한 후 배열을 출력해주려 하였다.

1. 1차원 배열(int []) + Arrays.sort()의 경우 문제는 해결되지만, 시간이 매우 오래 걸렸고

2. ArrayList + Collections.sort()의 경우 메모리 초과가 떴다.

3. 카운팅 정렬이 불필요하게 소모되는 메모리가 많아 별로일 것이라 생각했는데 예상외로 카운팅 정렬의 메모리가 가장 적게 잡혔고, 1차원 배열, ArrayList순으로 메모리가 많이 잡혔다. 카운팅 정렬이 입력되는 수의 범위가 한정적일 때(적당히) 다른 정렬보다 효율적이라는 것을 알게 되었다.

 

---

문제 원본

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

10989번: 수 정렬하기 3