30/06/2019 문제의 재탕임

문제

원소가 0, 1, 2로 구성된 배열이 주어졌을 때, 상수 공간을 이용해 선형 시간에 배열을 정렬하시오.

Input

[0, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 0]

Output

[0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2]

답

void sort012(int in[], int out[], int n) {
  int i, j, n[3] = {0, };
  for (i = 0; i < n; i++) {
    n[in[i]]++;
  }
  for (i = 0 ; i < 3; i++) {
    for (j = 0; j < n[i]; j++) {
      out[j] = i;
    }
  }
}