[Baekjoon] 2751 수 정렬하기 2 - JAVA

 

문제

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

 

---

✏️ 제출 답안

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int repeat = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < repeat; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for (int i : list) {
            sb.append(i).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

단순 숫자 정렬문제라 어렵지 않아서 효율을 높이려고 BufferedReader와 StringBuilder를 사용했다. 처음에는 배열에 저장하고 Arrays.sort()로 정렬했었다. 그런데 시간이 너무 길게 나온거 같아서 찾아보니 ArrayList를 쓰면 시간을 줄일 수 있다고 해서 ArrayList로 선언해서 Collections.sort()로 정렬하여 재제출했다. 큰 차이는 없지만 조금이라도 효율을 올릴 수 있었다.

 

 

🪄 Arrays.sort() vs. Collections.sort()

 

 배열과 컬렉션의 차이 

• Arrays.sort(): 배열을 정렬할 때 사용된다. 기본적으로 오름차순으로 배열의 요소를 정렬하며, int[], String[] 등과 같은 배열 타입에 적용할 수 있다.
• Collections.sort(): 리스트(List)를 정렬할 때 사용된다. 예를 들어 ArrayList와 같은 List 인터페이스를 구현하는 컬렉션에서 사용된다.

 정렬 방식 

• Arrays.sort(): 기본적으로 배열의 원시 타입 및 Comparable 인터페이스를 구현한 객체 배열에 대해 오름차순 정렬을 수행한다.
• Collections.sort(): 리스트의 요소들이 Comparable 인터페이스를 구현해야 하며, 기본적으로 오름차순 정렬을 수행한다. Comparator를 제공하여 사용자 지정 정렬을 할 수도 있다.

 성능 

• Arrays.sort(): 원시 타입 배열을 정렬할 때 성능이 최적화되어 있으며, Dual-Pivot Quicksort 알고리즘을 사용한다.
• Collections.sort(): 내부적으로 List를 배열로 변환한 후 정렬하므로, 배열 기반의 Arrays.sort()보다 다소 성능이 낮을 수 있다. 일반적으로 TimSort 알고리즘을 사용한다.

 

ArrayList와 같은 컬렉션을 사용하는 것이 일반적인 배열보다 성능이 더 높게 나온 이유

→ ArrayList가 유동적으로 요소를 추가할 때 메모리 재할당이 더 적게 발생하여 오히려 성능이 더 좋게 나올 가능성도 있다.

 

제출 현황