[백준/자바] 10989 수 정렬하기 3 (삽입 정렬, 합병 정렬, 힙정렬, 계수 정렬)

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

 

 

📌 문제 

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

 

 

⚔ 입력

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

 

 

📣 출력

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

 

 

 

 

---

 

 

 

💡 코드 구현

 

 

다음은 시간 초과가 발생한 코드이다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {
	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		int N = Integer.parseInt(bufferedReader.readLine());

		int[] numbers = new int[N];
		int first = Integer.parseInt(bufferedReader.readLine());
		numbers[0] = first;
		for (int i = 1; i < N; i++) {
			int number = Integer.parseInt(bufferedReader.readLine());

			numbers[i] = number;
			compare(number, numbers, i - 1);

		}

		// System.out.println("numbers = " + Arrays.toString(numbers));
		IntStream.range(0, numbers.length).forEach(i-> System.out.println(numbers[i]));
	}

	private static void compare(int number, int[] numbers, int idx) {
		if (idx < 0) {
			return;
		}

		if (number < numbers[idx]) {
			numbers[idx + 1] = numbers[idx];
			numbers[idx] = number;
		}

		compare(number, numbers, idx - 1);
	}
}

 

 

위의 코드는 삽입 정렬을 데이터 인풋과 동시에 정렬하도록 구현한 재귀 함수 compare를 사용한 정렬 방식이다.

 

이 코드는 입력된 수의 개수 N에 비례하여 재귀 호출을 수행하므로 시간 초과가 발생할 수 있다.

 

시간 복잡도를 분석해보면 다음과 같다. .

 

첫 번째 수를 입력받은 후, 두 번째부터 N번째 수까지를 입력받으면서 수를 정렬하는 과정에서 재귀 호출이 이루어진다. 따라서 N-1번의 재귀 호출이 발생하게 되는데, 이는 입력된 수의 개수 N에 비례한다.

 

재귀 호출 중에는 compare 함수 내에서 배열을 이동하고 비교 연산을 수행한다. 이동 연산은 배열의 길이에 비례하는 시간이 소요되므로, 한 번의 재귀 호출에서 수행되는 이동 연산은 최대 N번 발생할 수 있다.

 

따라서 이 코드의 시간 복잡도는 대략적으로 O(N^2)이다. 입력된 수의 개수가 10,000,000개인 경우, 최악의 경우 100,000,000,000,000번의 연산이 필요하게 되므로 시간 초과가 발생하게 된다.

 

만약 퀵정렬을 사용하면 어떨까? 

 

 

퀵 정렬은 분할 정복(divide and conquer) 방식을 사용하여 수를 정렬하는 알고리즘이다. 주어진 수를 기준(pivot)을 기준으로 작은 수와 큰 수로 나누어 재귀적으로 정렬하는 방식으로, 평균 시간 복잡도 O(nlogn)의 복잡도를 갖는 한편, 최악의 경우 O(n^2)의 복잡도를 갖는다.

 

입력 데이터 개수가 10,000,000이므로, 평균을 계산하면 약 230,000,000 번의 연산을 수행한다고 할 수 있다. 1억을 1초로 가정하면 이는 제한 시간인 5초(자바 3초)에는 가능할거 같기도 한 연산이다. 그러나 최악의 경우를 고려하면 연산 횟수는 100,000,000,000번에 이르게 된다. 이 경우 5초(자바 3초)보다 훨씬 많은 연산이 들어가 시간 초과를 피하지 못하게 된다. 

 

메모리 제한이 8MB(자바 512MB)인 경우를 고려하면 병합정렬을 사용하기도 힘들다. 

 

그렇다면 마지막 대안인 힙정렬은 어떠할까? 

 

힙정렬은 최악의 경우에도 O(nlogn)의 시간 복잡도를 가지므로 이 경우 제한 시간 내에 문제를 해결할 수 있는 정렬 방식이 될 수 있다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class Main {

   // 힙정렬을 이용한 풀이
   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(bufferedReader.readLine());

      int[] numbers = new int[N];
      for (int i = 0; i < N; i++) {
         int number = Integer.parseInt(bufferedReader.readLine());
         numbers[i] = number;
      }

      heapSort(numbers);

      // System.out.println("Sorted numbers: " + Arrays.toString(numbers));
      IntStream.range(0, numbers.length).forEach(i -> System.out.println(numbers[i]));

   }

   private static void heapSort(int[] arr) {
      int n = arr.length;

      // 힙 구성 (배열 재정렬)
      for (int i = n / 2 - 1; i >= 0; i--)
         heapify(arr, n, i);

      // 하나씩 요소를 힙에서 추출하여 정렬
      for (int i = n - 1; i > 0; i--) {
         // 현재 루트를 배열의 끝으로 이동
         int temp = arr[0];
         arr[0] = arr[i];
         arr[i] = temp;

         // 축소된 힙에 대해 최대 힙 구성
         heapify(arr, i, 0);
      }
   }

   private static void heapify(int[] arr, int n, int i) {
      int largest = i; // 최대값을 루트로 초기화
      int left = 2 * i + 1; // 왼쪽 자식 = 2*i + 1
      int right = 2 * i + 2; // 오른쪽 자식 = 2*i + 2

      // 왼쪽 자식이 루트보다 큰 경우
      if (left < n && arr[left] > arr[largest])
         largest = left;

      // 오른쪽 자식이 지금까지의 최대값보다 큰 경우
      if (right < n && arr[right] > arr[largest])
         largest = right;

      // 최대값이 루트가 아닌 경우
      if (largest != i) {
         int swap = arr[i];
         arr[i] = arr[largest];
         arr[largest] = swap;

         // 영향을 받은 하위 트리 재귀적으로 힙 구성
         heapify(arr, n, largest);
      }
   }
}

 

 

그래서 구현한 힙정렬을 돌려보았는데 결과는 

 

 

역시나 시간 초과가 떴다. 

 

약 2억 3천만 번의 연산이라 이론적으로는 3초 내에 수행되어야 하지만, 여러 요인등으로 이론 횟수보다 더 시간이 들어간다고 추론하였다. 

 

따라서 이 문제는 현존하는 비교 기반 정렬 알고리즘으로는 풀 수 없다. 비교 기반의 성능 하한은 O(nlogn)이기 때문이다. 

 

이 문제는 계수 정렬을 이용한 풀이가 필요하다. 즉, 데이터에 대한 메타 정보가 주어진 상황에서 데이터의 분포를 이용한 정렬 알고리즘을 사용해야 한다. 

 

계수 정렬의 종류로는 계수 정렬(counting 정렬), 기수 정렬(radix) 정렬이 있으며 선형 시간 복잡도 O(n)을 갖는다. 

 

카운팅 정렬을 사용해서 풀이해보면 다음과 같다. 

 

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

public class Main {

   private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(bufferedReader.readLine());

      int[] occurrences = new int[10000 + 1];
      while (N-->0) {
         occurrences[Integer.parseInt(bufferedReader.readLine())]++;
      }

      // System.out.println("Sorted numbers: " + Arrays.toString(occurrences));

      StringBuilder stringBuilder = new StringBuilder();

      for (int i = 0; i < occurrences.length; i++) {
         int occurrence = occurrences[i];
         while (occurrence != 0) {
            stringBuilder.append(i).append("\n");
            occurrence--;
         }
      }

      System.out.println(stringBuilder);
   }
}

 

 

 

 

 

이 코드의 시간 복잡도는 다음과 같다. 

 

i) 입력을 받는 부분 : O(N)

ii) 카운팅을 탐색하는 반복문 부분: O(max(10000, N));

 

따라서 O(N) 

 

따라서 문제 시간 조건을 만족시킨다. 

 

하지만, 문제에서 요구하는 대로 답을 출력하는 방식으로 System.out.println()을 사용하지 않고 stringbuilder를 사용하였는데, 표준 입출력의 경우 1000만번 호출이 된다면 마찬가지로 시간 초과를 발생시키기 때문이다. 

 

 

 

 

 

---

그런데 만약에 현재의 문제 조건처럼 숫자의 범위가 1 ~ 10000이 아니라 최대 10억이라고 하면 어떨까? 

1,000,000,000  * 4byte

=> 4,000,000,000byte

=> 4,000,000kB

=> 4,000MB

 

4기가를 넘어 버리므로 메모리가 커져버려 사용하기 힘든 방식이 된다

 

---