[백준] 1713 - 후보 추천하기

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

1713번: 후보 추천하기

 이문제 또한 특별한 알고리즘보단 구현력을 요구하는 문제다. 3회 시도만에 성공했는데 이게 정보올림피아드 초등부 1번이라니 -_-;;; 구현시 주의해야할 부분은 이정도다.

- 정렬함수 qsort나 sort를 쓸때 정렬 규칙을 커스텀해야 한다.
- 간단하게는 배열이나, STL을 사용한다면 벡터를 이용해 인덱싱을 통한 자료 접근에 대한 구현해야 한다.

 코드가 심각하게 지저분하다;;; STL을 사용했다면 조금 깔끔하게 짤수 있었을 것 같은데... 어쨌든 통과.

#include <iostream>
using namespace std;
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

typedef struct _student {
    int pictureIdx;
    int recommendedCnt;
    int lastPictured;
} student;

int cmp(const void *a, const void *b){
    if((*(student *)a).recommendedCnt != (*(student *)b).recommendedCnt){
        return (*(student *)a).recommendedCnt > (*(student *)b).recommendedCnt;
    }
    else {
        return (*(student *)a).lastPictured > (*(student *)b).lastPictured;
    }
}

student students[101];
int pictured[20];
int N, R;

int main(){
    memset(pictured, 0x00, sizeof(pictured));
    memset(students, 0x00, sizeof(students));

    scanf("%d", &N);
    scanf("%d", &R);
    for(int i=0; i<R; ++i){
        int in;
        scanf("%d", &in);
        bool isSet = false;
        for(int j=0; j<N; ++j){
            if(pictured[j] == 0){
                pictured[j] = in;
                students[in].pictureIdx = j;
                students[in].recommendedCnt += 1;
                students[in].lastPictured = i;
                isSet = true;
                break;
            }
            if(pictured[j] == in){
                students[in].recommendedCnt += 1;
                isSet = true;
                break;
            }
        }
        if(isSet == false){
            student picOut[101];
            for(int j=0; j<N; ++j){
                picOut[j].pictureIdx = j;
                picOut[j].recommendedCnt = students[pictured[j]].recommendedCnt;
                picOut[j].lastPictured = students[pictured[j]].lastPictured;
            }
            qsort(picOut, N, sizeof(student), cmp);
            students[pictured[picOut[0].pictureIdx]].pictureIdx = 0;
            students[pictured[picOut[0].pictureIdx]].recommendedCnt = 0;
            pictured[picOut[0].pictureIdx] = in;
            students[in].pictureIdx = picOut[0].pictureIdx;
            students[in].recommendedCnt += 1;
            students[in].lastPictured = i;
        }
    }
    sort(pictured, &(pictured[N]));
    for(int i=0; i<N; ++i){
        printf("%d ", pictured[i]);
    }
    printf("\n");

    return 0;
}