[C++] 백준 1713번 풀이 ( 후보 추천하기 )

- 문제 ( 1713번 ) : 후보 추천하기

• 링크 : https://www.acmicpc.net/problem/1713

• 일정기간동안 추천받은 학생의 사진을 홈페이지에 게시하려고 한다.
  이 때, 게시할 수 있는 사진의 수와, 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 사진이 홈페이지에 게시되는 학생이 누구인지 구하는 프로그램.

  • ex) 게시될 수 있는 사진의 수 : 3, 추천 : 1, 6, 8, 1, 5
    => 최종 게시 학생 : 1, 5, 8
    ( 추천수가 많은 학생 선정 ( 같다면 가장 늦게 추천받은 학생 게시 ) )

---

- 입력 및 출력

[ 입력 ]

• 첫째 줄에 게시할 수 있는 사진 개수 ( 1 ≤ N ≤ 20 ) 입력
• 둘째 줄에 받고자 하는 총 추천 횟수 ( 1 ≤ k ≤ 1,000 ) 입력
• 셋째 줄에 추천받은 학생을 나타내는 번호 ( 1 ≤ num ≤ 100 ) 가 공백을 사이에 두고 입력

[ 출력 ]

• 홈페이지에 사진이 게재된 최종 학생번호를 오름차순 ( 증가하는 순서 ) 으로 출력.

---

- 문제 풀이

• 이번 문제는 시뮬레이션 및 구현 문제이다보니 문제에 주어진 과정대로 따라가며 구현하면 쉽게 해결되는 문제이다.

• 이번 후보 추천하기 문제에서 나는 아래와 같이 5가지의 과정으로 나눠서 구현해보았다

  1. 비어있는 사진 틀 생성
  2. 사진틀에 입력받은 추천학생이 존재하는지 확인
  3. step2 가 true 라면 추천수만 up || false 라면 사진틀에 넣고 추천수 up
  4. 추천받은 학생에 대해 전부 작업을 완료했다면 오름차순 정렬
  5. 정렬되어있는 사진틀 출력

• 이번 문제를 해결하면서 자료구조는 아래와 같이 사용했다.

  • 사진을 업로드하는 사진틀 : vector
    ( ∵ 사진을 정렬해 기준에 맞는 사진을 넣었다가 뺐다가 해야하므로 )
    
    
  • 추천 수 저장 : array
    ( size : 모든 학생의 수 ( 100명 ) )
    
    
  • 사진을 정렬할 때 필요한 기준인 업로드 된 기간 : array
    ( size : 모든 학생의 수 ( 100명 ) )

• 위에 세부적으로 나눈 step 을 따라서

  1) 사진틀 vector 를 생성하고,
  2) 사진틀에 입력받은 학생이 존재하는지 확인해서
  3-1) 사진틀에 이미 있다면 그 학생의 추천수만 up
  3-2) 사진틀에 존재하지 않는다면 사진틀에 넣고 추천수 up
  4) 사진틀에 넣을 때 사진틀이 전부 채워져있다면 추천수가 가장낮고, 이러한 학생이 여러명이면 가장 예전에 추천받은 학생을 뺀 후 그 자리에 추천받은 학생 업로드
  5) 추천받은 학생들을 전부 위와 같은 작업을 수행했다면 오름차순 정렬
  6) 정렬되어있는 학생들 출력

  하면 문제 해결!
  

• 원래 시뮬레이션 및 구현 문제를 해결할 때 각 step 들을 함수로 선언해주어 main 함수 안에서는 각각의 step 만 나열하는 식으로 문제를 해결했었다.

  이번에는 몇가지 함수 정의를 하지 않고 main 에서 각각에 step 에 맞는 작업을 수행하도록 구현했는데 가독성 부분에서 각 step 을 함수로 선언해주어 나열하는 방법으로 구현하는것이 좋은 것 같다는 생각이 들었다.

---

- 최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define NUM_MAX 101
using namespace std;

// step1. 비어있는 사진 틀 생성
// step2. 사진틀에 입력받은 추천학생이 존재하는지 확인
// step3. step2 가 true 라면 추천수만 up || false 라면 사진틀에 넣고 추천수 up
// step4. 추천받은 학생에 대해 전부 작업을 완료했다면 오름차순 정렬
// step5. 정렬되어있는 사진틀 출력

// 전역변수 선언 (N : 사진틀의 개수, k : 친구들 추천 총 횟수)
int N = 0, k = 0;

// 사진틀에 저장된 시간 기록 배열 (추천이 될 때의 시간 기록할 배열)
// 이 배열에 들어간 값이 작을수록 오래된 것임.
int t[NUM_MAX] = {0, };

// 추천수 기록 배열
int num[NUM_MAX] = {0, };

// step1. 비어있는 사진 틀 생성 (사진을 계속 교체해야하므로 vector 로 생성)
vector<int> frame;

// 정렬할 때 사용하는 compare 함수
bool comp(int a, int b) {
    // 정렬기준1. 추천수가 같을 때 오래된 친구 제거 -> 기간에 따라 오래된 친구가 뒤로 가도록 정렬
    if(num[a] == num[b]) {
        if(t[a] > t[b]) {
            return true;
        } 
    }

    // 정렬기준2. 내림차순 정렬 (추천수가 적은 친구를 사진틀에서 제거해야하는데 가장 뒤에 있는 것이 편함.)
    else if (num[a] > num[b]) {
        return true;
    } else {
        return false;
    }

    return false;
}

// 사진틀에 추천받은 학생이 존재하는지 여부 판별 함수
bool exist (int student_number) {
    // 사진틀을 돌면서 student 가 존재하는지 확인
    for(int i = 0; i < frame.size(); i++) {
        if(frame[i] == student_number) {
            return true;
        }
    }

    // 위 조건에 한번도 걸리지 않았다면 존재하지 않음.
    return false;
}

int main () {
    // 사진틀의 개수 (N), 추천 총 횟수 (k) 입력
    cin >> N >> k;

    // 추천받은 학생을 나타내는 번호 빈칸을 두고 입력
    for(int i = 0; i < k; i++) {
        int student = 0;
        cin >> student;

        // step2. 사진틀에 추천받은 학생 있는지 확인
        // 사진틀에 추천받은 학생이 있다면 추천수만 up
        if(exist(student)) {
            num[student]++; // 추천수 up
        }

        // 사진틀에 추천받은 학생이 없다면
        else {

            // step3. 사진틀에 추천받은 학생 게시 
            // 사진틀이 비어있을 땐 바로 게시
            if(frame.size() < N) {
                frame.push_back(student);
            } 

            // 사진틀이 꽉 차있다면 
            // 1. 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제
            // 2. 1번 조건 학생이 여러명인 경우 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제
            else {
                // 위의 2가지 경우에 만족하는 학생을 제거하기 위해 사진틀 정렬
                sort(frame.begin(), frame.end(), comp);

                // comp 함수에 의해 2가지 경우에 만족하는 학생이 가장 뒤에 위치
                int remove_student = frame.back();
                t[remove_student] = 0;
                num[remove_student] = 0;

                // 즉 frame 의 가장 마지막원소를 제거한 후 추천학생 추가하면 됨.
                frame.pop_back();
                frame.push_back(student);
            }

            t[student] = i; // 사진틀에 들어간 시기 저장
            num[student]++; // 추천수 저장
        }       
    }

    // 사진틀을 학생번호에 대한 오름차순 정렬
    sort(frame.begin(), frame.end());

    // 사진틀에 저장되어있는 학생 출력
    for(int i = 0; i < frame.size(); i++) {
        cout << frame[i] << " ";
    }

    printf("\n");
    return 0;
}