백준 문제 풀이 - 정렬 단계 - 10989번 수 정렬하기 3 (브론즈1)

 

N개의 수가 주어졌을 때, 오름차순으로 정렬하는 간단한 프로그램 구현 문제이다.

중요한 것은 제한사항인데, 입력에는 중복된 값이 있을 수 있고, 최대 값은 10000이다.

나는 이전 수 정렬 문제들을 sort() 메서드를 이용하여 풀었는데 (이미 해당 메서드를 알고 있었다.) 이번 문제에서 카운팅 정렬과 sort()메서드의 속도를 비교해 보기로 하였다.

 

우선, 2751번 - 수 정렬하기 2 (실버 5) 에서 사용하였던 오름차순 정렬 코드를 살펴 보자.

---

 

 2751번 - 수 정렬하기 2 (실버 5)

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

위 문제 역시 오름차순으로 입력받은 값을 정렬하기만 하면 되는데, 두 문제의 차이는, 최대 값과 중복값의 여부이다.

다만, 위의 문제는 효율성을 검증하는 문제이기 때문에 입력값이 많아지더라도 속도가 보장되는 로직을 사용하는 것이 중요하였다.

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

class Main{
    public static int n;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        
        for(int i = 0; i < n; i++){
            arr.add(Integer.parseInt(br.readLine()));
        }
        
        Collections.sort(arr);
        StringBuilder sb = new StringBuilder();
        
        for(int num : arr){
            sb.append(num).append("\n");
        }
        
        System.out.println(sb.toString());
    }
}

나는 Collections.sort() 메서드를 이용하였는데, 처음에는 StringBuilder를 사용하지 않고 바로 System.out.println(num)으로 바로 출력하게 만들었더니 시간 초과가 나는것을 확인하였다.

처음에는 sort 메서드의 효율성 문제인 줄 알고 해당 메서드가 어떤 알고리즘으로 작동하는 지 찾아보았는데, 해당 메서드는 Timsort 알고리즘인 것을 확인하였다.

쉽게 설명하면 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 섞은 것인데, 시간 복잡도 상으로 O(n) ~ O(nlogn)을 보장하기 때문에 정렬 알고리즘 자체의 문제는 아닌 것으로 판단하였다.

굉장히 정리가 잘 되어있는 글을 소개하니 자세하게 알고 싶은 사람은 참고해도 좋을 것 같다.

 

https://st-lab.tistory.com/106

다시 한번 문제가 될 만한 곳을 생각해보니 입출력 단계에서 시간이 오래 걸린다고 판단하고 StringBuilder를 이용하여 한번에 출력하는 방법으로 바꾸니 정상적으로 출력되는 것을 확인 할 수 있었다.

참고로, Arrays.sort()와 Collections.sort()는 정렬 알고리즘이 다른지라 시간이 좀 차이가 나는데

위의 것이 Collections.sort()를 사용한 것이고 아래가 Arrays.sort()로 구현한 것이다.

메모리와 시간에서 어느정도 차이가 나는 것을 확인 하였다. (크게 유효한 의미인지는 잘 모르겠다...)

---

본론으로 돌아와서...

정렬 알고리즘을 파보며 카운팅 정렬이란 것을 알게 되었는데, 이번 문제를 풀어보며 Collections.sort()와 비교해보기로 마음 먹었다.

우선 카운팅 정렬이 뭔지 알아보자.

 

 

카운팅 정렬이란, 정수 또는 제한된 범위의 정수를 정렬하는데 효과적인 비교 정렬이 아닌 정렬 알고리즘 이다.

카운팅 정렬은 카운팅이라는 말처럼 값들을 비교하는 것이 아닌 빈도를 세어 정렬하는 방식으로 동작한다.

동작 과정은 다음과 같다.

1. 카운트 배열 생성: 정렬하려는 데이터의 범위 내에 있는 모든 가능한 값에 대한 카운트(빈도)를 저장하기 위한 카운트 배열을 생성한다. 이 배열은 정렬하려는 데이터 범위의 크기와 같다.
2. 카운트 생성: 입력 데이터를 읽으면서 각 데이터의 값에 해당하는 카운트를 증가시킨다. 즉, 입력 데이터를 순회하면서 카운트 배열의 각 인덱스에 해당하는 값을 증가시킨다.
3. 누적 카운트 생성: 누적 카운트 배열을 생성한다. 누적 카운트 배열은 각 값의 빈도 누적 합을 저장하는 배열로, 각 값 이후에 등장하는 데이터의 위치를 알 수 있도록 돕는다.
4. 출력 배열 생성: 정렬된 데이터를 저장하기 위한 출력 배열을 생성한다. 이 배열의 크기는 입력 데이터의 크기와 같다.
5. 정렬: 입력 데이터를 순회하면서 해당 데이터의 값에 해당하는 누적 카운트를 참조하여 정렬된 위치에 데이터를 배치한다. 이 과정에서 카운트를 감소시키면서 중복된 값에 대해 처리한다.
6. 출력: 정렬된 데이터가 출력 배열에 저장되며, 이 배열이 정렬된 결과를 나타낸다.

동작 과정을 보면 알 수 있지만, 카운팅 정렬은 미리 배열의 크기를 정해야 하기때문에 입력되는 값이 반드시 음이 아닌 정수이며 입력 되는 값의 범위가 작을때 사용 가능하다.

최대, 최소값의 차이가 100만 이하인 경우 효과적이라고 할 수 있는데, 제한적 환경에서 사용가능하지만 단일 for문으로 한번만 순회하면 처리가 끝나므로 시간복잡도는 O(n)으로 굉장히 빠르게 처리가 가능하다.

적용 방법은 쓰기 나름인데, 중복값이 없다면 boolean 타입의 배열을 만들어 처리해도 되고, 중복값이 존재한다면 int 배열로 해당 인덱스의 값을 ++시키면서 진행하다가 출력시에는 --시키면서 처리하면 한번에 처리가 가능하다.

 

구현한 코드는 다음과 같다.

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

class Main{
    public static int n;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] arr = new int[10001];

        for(int i = 0; i < n; i++){
            arr[Integer.parseInt(br.readLine())]++;
        }

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < arr.length; i++){
            if(arr[i]>0){
                sb.append(i).append("\n");
                arr[i]--;
                i--;
            }
        }
        System.out.println(sb.toString());
    }
}

앞서 설명한대로 int타입의 배열을 선언하고 크기는 10001로 선언하였다.(최대 범위가 10000이기 때문이다.)

그리고 입력 값 만큼 for문을 순회하면서 입력된 값의 index에 ++를 해준다.

이렇게 하면 중복값이 들어와도 해당 인덱스가 그 값의 갯수가 되기 때문에 정렬하는 것과 똑같은 효과를 볼 수 있다.

그 후 출력시에는 for문을 순회하며 해당 index의 값이 0보다 클때마다 StringBuilder에 append해준다.

(StringBuilder를 사용한 이유는 위에 설명한 것과 같이 출력 시간을 줄이기 위함이다.)

이후 StringBuilder를 출력하면 정상적으로 정렬 된 것을 확인 할 수 있다.

 

앞서 사용한 sort()메서드와 비교해보면 1번째가 카운팅 정렬, 2번째가 sort()메서드를 사용한 로직인데 메모리나 시간면에서 크게 차이가 나는 것을 확인 할 수 있었다. 특히 속도는 정말 많이 빨라졌는데, 위처럼 특정한 환경에서는 정말 빠른 처리가 가능한 것을 확인 할 수 있었다.