• 30/06/2019 문제를 간소화한 재탕임

문제

바이너리 배열(원소를 0, 1만 갖는 배열)이 주어졌을 때, 배열을 정렬하시오.
단, 시간 복잡도는 O(n), 공간 복잡도는 O(1).
결과는 0이 먼저 출력되고 1이 출력되어야 합니다.

Input

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

Output

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

답

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