[JAVA/백준/10989] 수 정렬하기 3 / 퀵 정렬, 배열

10989번: 수 정렬하기 3

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

www.acmicpc.net

java로는 제한 시간이 3초라 여유로울 줄 알고 단순 선택 정렬로 풀었지만 계속해서 시간 초과가 떴다..
그래서 퀵 정렬을 이용해서 풀어 2.5초로 성공했지만 다른 사람들 풀이를 보니 1초대로 나와 참고하며 다시 풀었다.

우선 퀵 정렬을 이용해서 푼 방법이다.

1. 퀵 정렬 이용

퀵 정렬은 말 그대로 빠른 정렬이다. O(n^2)의 시간 복잡도를 가지는 단순 선택 정렬과는 달리 평균적으로 O(nlogn)의 복잡도를 가진다고 한다.

1. 위에 사진과 같이 중간 순서의 값을 정한다.(파란 줄)

2. 중간값을 기준으로 왼쪽과 오른쪽에서 중간값으로 하나씩 탐색하며
왼쪽 탐색 값 > 중간값
오른쪽 탐색값 < 중간값
이 될 때까지 탐색하고 두 값을 교환한다.

3. 만약, 왼쪽 탐색 위치가 오른쪽 탐색 위치의 오른쪽으로 간다면 (서로 교차한다면) 그 위치를 기준으로 반을 나누어 위의 과정을 반복한다.

코드로 구현해보았다.

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


public class Main {


  static void swap(int[] arr, int x, int y) {
    int temp = arr[y];
    arr[y] = arr[x];
    arr[x] = temp;
  }

  static void quickSort(int[] arr, int left, int right) {
    int pl = left;
    int pr = right;
    int mid = arr[(pl + pr) / 2];

    do {
      while (arr[pl] < mid) {
        pl++;
      }
      while (arr[pr] > mid) {
        pr--;
      }
      if (pl <= pr) {
        swap(arr, pl++, pr--);
      }
    } while (pl <= pr);

    if (left < pr) {
      quickSort(arr, left, pr);
    }
    if (right > pl) {
      quickSort(arr, pl, right);
    }
  }

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int T = Integer.parseInt(br.readLine());

    int[] arr = new int[T];

    for (int i = 0; i < T; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }
    quickSort(arr, 0, T - 1);
    for (int i = 0; i < T; i++) {
      bw.write(arr[i]+"\n");
    }
    bw.flush();
    bw.close();
  }
}

수행 결과

퀵 정렬을 이용하면 간신히 통과한다.
다른 분들 풀이를 보니 정렬 자체를 안 하고 배열에 저장한 후 출력을 했다.

2. 배열과 버퍼 이용

1. 10001 크기의 배열을 선언한다 (1~10000까지의 숫자를 count 하기 위함)

2. 수를 입력받으면서 index가 일치하는 배열의 값을 count 한다.

3. 버퍼에 저장 후 출력한다.

여기서 repeat이라는 메서드를 볼 수 있다.
repeat()은 괄호 안에 주어진 파라미터 값만큼 반복을 한다. 중복 값을 깔끔하게 처리해 주는 메서드이다.

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[10001];
    for (int i = 0; i < n; i++) {
      arr[Integer.parseInt(br.readLine())]++;
    }
    for (int i = 1; i < arr.length; i++) {
      bw.write(String.valueOf(i + "\n").repeat(arr[i]));
    }
    bw.flush();
    bw.close();
  }
}