[BOJ-10825]국영수

https://www.acmicpc.net/problem/10825

[문제설명]

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

[문제풀이]

힙 자료구조, 힙에 넣을 때 비교함수를 만들어 볼 수 있는 좋은 문제라 생각한다.

헤더 없이 코드를 작성하였다. 

strcmp

node

heap

총 3가지를 작성할 수 있으면 풀 수 있는 문제이다.

[C++ Source Code]

#include<iostream>
 
bool m_strcmp(char* k1, char* k2) {
    while (1) {
        if (*k1 < *k2) return true;
        else if (*k1 == *k2) {
            if (*k1 == 0) break;
            k1++;
            k2++;
            continue;
        }
        else break;
        k1++;
        k2++;
    }
    return false;
}  
 
struct node {
    int kor;
    int eng;
    int mat;
    char name[11];
    node() {}
    node(int ik, int ie, int im) :
        kor(ik), eng(ie), mat(im) {}
    bool operator <(node n) {
        if (kor > n.kor) return true;
        else if (kor == n.kor) {
            if (eng < n.eng) return true;
            else if (eng == n.eng) {
                if (mat > n.mat) return true;
                else if (mat == n.mat) {
                    if (m_strcmp(name, n.name)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};
 
 
template<class T>
struct heap {
    T d[1 << 18];
    int e;
    heap() { e = 0; }
    bool empty() { return e == 0; }
    bool full() { return (e + 1) == (1 << 18); }
    T top() {
        T ret;
        if (empty()) return ret;
        return d[1];
    }
    void push(T input) {
        if (full()) return;
        d[++e] = input;
        int cur = e;
        while (cur / 2 > 0) {
            if (d[cur] < d[cur / 2]) {
                swap(d[cur], d[cur / 2]);
            }
            else break;
            cur /= 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        int cur = 1;
        while (2 * cur <= e) {
            int child;
            if (2 * cur + 1 > e) {
                child = 2 * cur;
            }
            else {
                if (d[2 * cur] < d[2 * cur + 1]) {
                    child = 2 * cur;
                }
                else {
                    child = 2 * cur + 1;
                }
            }
 
            if (d[cur] < d[child]) break;
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    void swap(T& a, T& b) {
        T t = a;
        a = b;
        b = t;
    }
};
node data[1 << 18];
heap<node> PQ;
int main() {
    //freopen("input.txt", "r", stdin);
    int N; 
    scanf("%d", &N);
    for (register int i = 0; i < N; ++i) {
        scanf("%s %d %d %d", data[i].name, &data[i].kor, &data[i].eng, &data[i].mat);
    }
    for (register int i = 0; i < N; ++i) {
        PQ.push(data[i]);
    }
    while (!PQ.empty()) {
        printf("%s\n", PQ.top().name);
        PQ.pop();
    }
    return 0;
}
 
// Op = 10 + 1 + 1 + 1
// Op * n log (n * Op)
// 13 * 100,000 = 1,300,000
// 21 * 1,300,000 = 27,300,000