10867 - 중복 빼고 정렬하기

 

10867번: 중복 빼고 정렬하기

 

힙 정렬 짜고

 

중복 체크하면 끝

 

#include <stdio.h>

const int LM = 1e5;
int N;
int R[LM];
int r;

void swap(int& x, int & y) { int z = x; x = y; y = z; }

int maxComp(int x, int y) { return x > y; }
int minComp(int x, int y) { return x < y; }

struct PQ {
  int hn;
  int heap[LM + 10];
  int (*comp)(int, int);

  void init(bool flag) {
    hn = 0;
    comp = flag ? minComp : maxComp;
  }

  void push(int n) {
    heap[++hn] = n;
    
    for (int c = hn; c > 1; c /= 2) {
      if (comp(heap[c], heap[c/2])) {
        swap(heap[c], heap[c / 2]);
      } else {
        break;
      }
    }
  }

  int pop() {
    swap(heap[1], heap[hn--]);

    for (int c = 2; c <= hn; c *= 2) {
      if (c < hn && comp(heap[c + 1], heap[c])) {
        c++;
      }

      if (comp(heap[c], heap[c / 2])) {
        swap(heap[c], heap[c / 2]);
      } else {
        break;
      }
    }

    return heap[hn + 1];
  }
} pq;

void init() {
  scanf("%d", &N);

  for (int n = 0; n < N; ++n) {
    int t;

    scanf("%d", &t);

    pq.push(t);
  }
}

void print() {
  R[r] = pq.pop();

  int p;

  while (pq.hn) {
    p = pq.pop();

    if (R[r] != p) {
      R[++r] = p;
    }
  }

  for (int i = 0; i <= r; ++i) {
    printf("%d ", R[i]);
  }
}

int main(void) {
  // freopen("10867.txt", "r", stdin);

  pq.init(1);

  init();

  print();

  return 0;
}

 

삼성아 고마워 !