2. SendMessage (구조체 배열1, IDX 구조체 배열1, Linked list 2, heap)

 

문제 접근

보통 timestamp가 있는 문제는 사실 timestamp가 중요하지 않거나 고작 time을 주는 용도로만 쓰인 다는 것을 명심.

그리고 이번 문제 처럼 timestamp를 idx 구조체 배열에 하나의 time 변수로 설정해서 그걸 heap으로 관리하는 문제가 많다는 것을 알기.

그래서 이번 문제에서도 timestamp를 딱 보면 바로 heap으로 이 시간을 관리해야 하는구나,,! 라는 생각을 바로 해야한다.

 

또한, 각각의 user 마다 send랑 receive의 개수는 중요하지 않고 심지어 앞에서 3개라고 하니 바로 linked list를 떠올렸어야 했다.

여기서 다행히 user, mid는 개수를 10^6이하로 주웠기에 따로 hashing을 해야 하는 귀찮은 작업은 덜었다.

항상 user의 uid 값이 크지 않다면 hashing을 하지 않아도 된다는 것을 유념하자.

 

만약 여기서 문제가 업그레이드 되었다면 쪽지 별로 update를 할 수 있는데 그때도 heap을 사용하는 것이 update()함수를 사용하여서 linked list의 가장 앞으로 보내주면 된다.

 

자료구조

출처 입력

user를 담을 user 구조체 배열 1개와

그 안에 linked list 2개씩

그리고 mid를 담을 IDX 구조체 배열 1개

그 IDX를 가지고 정렬하는 heap 1개

이렇게 총 5개의 자료구조가 필요하다.

#define MAXM	3
#define HISZE 100000
struct Hash {
    int maidx;
    Hash* next;
    Hash* alloc(int _maidx, Hash* _next) {
        maidx = _maidx;
        next = _next;
        return this;
    }
}buf[400000];
int bfcnt, maidx;
struct User {
    Hash send, rece;
}user[1001];
struct Mst {
    int sendUid, receUid, mID, timesp;
    int isRead, del;
    void init(int _sendUid, int _receUid, int _mID, int _timesp) {
        sendUid = _sendUid; receUid = _receUid; mID = _mID; timesp = _timesp;
        isRead = 0;
        del = 0;
    }
}marr[100001];
bool cmp(int a, int b){
    if (marr[a].timesp > marr[b].timesp) return true;
    else return false;
}
void swap(int& a, int& b) {
    int c = a;
    a = b;
    b = c;
}
struct Heap {
    int mid[200001], size;
    void update(int child) {
        int parent = child / 2;
        while (child != 1 && cmp(mid[parent], mid[child])) {
            swap(mid[parent], mid[child]);
            child = parent;
            parent /= 2;
        }
    }
    void downdate(int parent) {
        int child = parent * 2;
        while (child <= size) {
            if (child + 1 <= size && cmp(mid[child], mid[child + 1])) child++;
            if (cmp(mid[child], mid[parent])) break;
            swap(mid[parent], mid[child]);
            parent = child;
            child *= 2;
        }
    }
    void push(int _midx) {
        mid[++size] = _midx;
        update(size);
    }
    int pop() {
        if (size == 0) return -1;
        int res = mid[1];
        mid[1] = mid[size--];
        downdate(1);
        return res;
    }
}heap;