BOJ02751 수 정렬하기 2

https://www.acmicpc.net/problem/2751 (opens new window)

java 내부의 정렬 메소드를 활용하여 해결하였다. List 인터페이스의 sort 메소드는 default 메소드로 선언되어 있기 때문에 Collections 유틸 클래스를 사용하지 않아도 적용이 가능하다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BOJ2751 {

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

        int n = scanner.nextInt();
        List<Integer> numbers = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            numbers.add(scanner.nextInt());
        }

        // Collections.sort(numbers) -> 내부적으로 같다. list.sort(null)로 처리된다.
        numbers.sort(null); 
        StringBuilder stringBuilder = new StringBuilder();
        for (Integer number : numbers) {
            stringBuilder.append(number).append("\n");
        }
        System.out.println(stringBuilder);
    }
}

다른 방법으로는 counting sort를 활용하는 것이다. counting sort는 요소의 값을 비교하지 않고 배열에 저장하기 때문에 O(n) 의 시간복잡도로 굉장히 빠른 속도를 자랑한다. 하지만 추가적인 배열이 소모되기 때문에 메모리가 낭비될 우려가 있다.

또한 배열에 표현하기 위해 숫자로 이루어진 리스트에만 적용이 가능하다.

아래는 counting sort를 적용한 제출 코드이다.

public class BOJ2751 {

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

        int n = scanner.nextInt();
        boolean[] array = new boolean[2_000_001];

        for (int i = 0; i < n; i++) {
            array[scanner.nextInt() + 1_000_000] = true;
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            if (array[i]) {
                stringBuilder.append(i - 1_000_000).append("\n");
            }
        }
        System.out.println(stringBuilder);
    }
}

#algorithm #BOJ #정렬 #계수 정렬