[BOJ] 10989번: 수 정렬하기 3

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

 

이 문제는 입력받은 숫자를 오름차순으로 정렬하는 문제로, 시간제한은 자바 기준 3초, 메모리 제한은 8MB이다. 처음에 시간제한이 3초로 넉넉하길래 '간단하겠는데?'라고 생각했던 건 나의 크나큰 오산이었다...

---

우선 첫 번째 나의 시도는 Arrays.sort() 메소드 사용하기였다.

시도 1) Arrays.sort()

import java.util.Arrays;
import java.util.Scanner;

// Arrays.sort
public class BOJ_10989 {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);

        int N = sc.nextInt();
        int []arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        for (int i = 0; i < N; i++) {
            System.out.println(arr[i]);
        }
    }
}

실행과 입출력 결과 모두 올바르겠지만, 시간 초과이다.

추후 든 생각이지만 아마 Scanner 대신에 BufferedReader로 입력을 받고, 출력도 StringBuilder를 사용했더라면 시간 초과는 나오지 않았을 수 있겠다.

 

---

 

시도 2) Quick Sort와 Merge Sort

어찌 됐든간 시간을 줄여야한다는 생각에 이후 나는 퀵 정렬과 합병 정렬 코드까지 짰었다. (코드를 짜며 다시 한 번 퀵 정렬과 합병 정렬 개념을 복습할 수 있었는데, 이 내용은 추후 블로그로 또 정리해보려 한다.)

'시간 복잡도가 O(nlogn)인 Merge Sort까지 시간 초과라니... 무슨 일이야?!'라는 생각에 적잖이 당황했다.

 

다시 문제 조건을 읽어보자. 주목해야 할 것은 바로 메모리 제한(8MB)이다. 이 전에 풀었던 2750, 2751번 정렬하기(선택 정렬, 합병 정렬로 해결했었음)는 시간제한이 1-2초로 짧은 대신 메모리 제한은 256-512MB로 굉장히 넉넉하다. 

 

고민에 빠져 문제를 어떻게 해결할지 찾아보다, 계수 정렬(Counting Sort)로 이 문제를 해결할 수 있다는 걸 알게 되었다.

 

---

 

시도 3-1) Counting Sort

사실 카운팅 정렬을 배운 지 꽤 되어서인지, 아예 까먹고 있었다... 하하 우선 계수 정렬의 개념부터 차근차근 알아보자.

Counting Sort는 배열 요소를 직접 서로 비교하는 것이 아니라 인덱스를 활용하는 정렬 방법이다. 전체적인 흐름은 다음과 같다.

 

배열 요소를 우선 한 번 순회하여, 각 값(요소)이 배열에서 총 몇 개 있는지 세어야 한다. 총 몇 개 있는지 세었던 값은 새로운 다른 배열에 저장해 주자.(count) 특정 값을 인덱스로 하는 배열 칸에, 그 값의 count 된 횟수를 저장하는 것이 포인트이다. (예를 들어, 원래 배열에서 1이 세 번 나왔다면 count[1] = 3일 것이다. 4는 원래 배열에 한 개만 있었다면 count[4] = 1이다.) 이제, count 수가 담긴 배열의 인덱스(즉, 원래 배열의 요소 값)를 처음부터 끝까지 오름차순으로 count 수만큼 넣어 정렬하면 된다. (정렬해 보자면 1 1 1 4...)

 

이 정렬에는 총 3개의 배열이 필요하다. 원래 배열, count 배열, 정렬할 배열 이렇게 3가지이다.

자세한 내용은 그림으로 표현하면 더 이해하기 쉽다.

 

만약 다음과 같은 A 배열이 있을 때 count 배열과 sorted 결과는 다음과 같을 것이다.

이렇게 그대로 정렬 알고리즘을 짜도 되지만, count 배열에서 이전 요소와 현재 요소를 더해 현재 배열 칸을 바꿔주는 누적합(accumulated) 배열도 만들어볼 수 있다.

 

count[i] += count[i-1]

accumulated 배열은 마지막 정렬 단계에서, 원래 배열 값을 어디 인덱스(위치)에 넣을지 파악하기 좋은 수단이다.

왜냐하면 (accumlated 배열 값 - 1)은 i가 위치할 인덱스를 의미하기 때문이다.

 

count[i]-1를 sorted의 인덱스로 하여, 뒤에서부터 count 수만큼 배열을 채워주면 (count 값이 0, 즉 원래 배열에 없던 수는 당연히 sorted에 넣을 필요가 없다.) 최종으로 계수 정렬된 배열을 얻을 수 있다.

 

처음에는 이 로직을 토대로 코드를 혼자서 짜보았다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// Counting Sort
public class BOJ_10989_4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int []arr = new int[N];
        int []count_old = new int[10000];

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

        int max = arr[0];
        for (int i = 0; i < N; i++) {
            if(max < arr[i])
                max = arr[i];
        }
        
        // Counting Sort
        int []sorted = new int[N];

        int i = N-1;
        int j = max-1;
        while(i>=0) {
            if (count_old[j] > 0) {
                sorted[i] = j+1;
                count_old[j]--;
                i--;
            }


            else if (count_old[j] == 0 && j == 0) {
                sorted[i] = 0;
                i--;
            }

            else if (count_old[j] == 0) {
                j--;
            }
        }

        for (int k = 0; k < N; k++) {
            System.out.println(sorted[k]);
        }
    }
}

로직은 맞는 것 같은데, 왜?!

생각해 보면 앞서 말했듯이 Counting Sort는 배열 요소를 직접 서로 비교하는 것이 아니라 인덱스를 활용하는 정렬 방법이다. 그런데 나의 코드를 보면 결국 정렬할 때 count 배열의 인덱스 j(원래 배열 요소 값)가 0일 때... 라는 조건문이 나오면서 결국 배열 요소의 값을 확인해 준다는 점에서 계수 정렬의 의도에서 빗겨나갔다.

 

"배열을 쭉 돌며 각 값의 count를 세고, 그 인덱스 값을 차례로 각 count 수만큼 새 정렬 배열에 넣는다." 한 번 배열 쭉 도는 게 다인 Counting Sort는 역시 시간 복잡도가 O(n)으로 매우 매우 작을 수밖에 없는 것이다.

 

그리고 코드를 짜다 보니 알게 된 것이지만, Counting Sort 구현 시에는 굳이 accumulated array가 필요하지 않다. count 누적합을 구해 줄 필요도 없이, 위 설명처럼 그냥 원래 count 배열을 이용해서 count 수(0 이상)만큼 인덱스인 i를 앞에서부터 마지막 10000까지 쭉 출력해주기만 하면 된다.

 

시도 3-2) Counting Sort (최종⭐️)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            count[arr[i]]++; // 입력과 동시에 count (인덱스=배열 요소, 값=그 배열 요소의 개수)
        }

        br.close();
        
//        // count_new (accumulated) 만들기
//        for (int i = 1; i < count.length; i++) {
//            count[i] += count[i-1];
//        }

//        for (int i = N-1; i >=0; i--) {
//            int value = arr[i];
//            count[value]--;
//            sorted[count[value]] = arr[i];
//
////            sorted[count[arr[i]] - 1] = arr[i];
//        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < 10001; i++) {
            while(count[i]>0){
                sb.append(i).append("\n");
                count[i]--;
            }
        }
        System.out.println(sb);
    }
}

주석 처리된 부분은 accumulated array가 필요하지 않다는 점을 깨달은 부분...

 

성공!

 

---

정렬 알고리즘을 구현할 때마다 아직 어려워서 스트레스를 받는데, 계수 정렬 역시 이론을 코드로 짤려니 인덱스가 배열 값이고 배열 값이 또 다른 배열의 인덱스고...하니 처음에는 헷갈려 죽는 줄 알았다. 하지만 천천히 차근차근 생각하고 그림도 그려보며 마지막으로는 효율적인 코드에까지 다다르게 되었다...! 잊지 않고 다음에 주어진 메모리가 제한된 문제를 풀 때 써야 할 일이 있다면 잘 활용해 보아야겠다!