[JAVA]백준 1713번: 후보 추천하기

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

1713번: 후보 추천하기

1. 문제 설명

 

1) 어떤 학생이 특정 학생을 추천하면 추천받은 학생의 사진은 반드시 사진틀에 게시된다.

2) 비어 있는 사진틀이 없는 경우에는 현재까지 추천받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다.

3) 현재까지 추천받은 횟수가 가장 적은 학생이 두 명 이상인 경우에는 그러한 학생 들 중 게시된 지 가장 오래된 사진을 삭제한다.

4) 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우 추천받은 횟수만 증가시킨다.

5) 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천 받은 횟수는 0으로 바뀐다.

 

사진들의 개수와 전체 학생의 추천 결과가 추천 받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 문제.

 

2. 풀이

 

문제 그대로 구현하면 된다.

 

후보가 사진틀에 들어가는 위치를 changeIdx라고 하자.

 

그럼, 사진틀이 비어있거나 사진틀에 걸려있는 후보가 현재 사진틀에 게시하고자 하는 후보와 같은 경우 현재 인덱스를 changeIdx로 하고 탐색을 종료하면 된다.

 

만약 두가지 경우에 해당하지 않는다면, 사진틀에 게시된 학생들 중에 제일 추천수가 적거나, 추천수가 같은 학생이 여러 명이면 그중 먼저 걸린 학생을 찾아야 한다.

따라서 두가지 조건에 해당하는 학생을 반복문을 돌면서 찾는다.

 

그 후, changeIdx 사진틀에 게시되어 있는 학생이 현재 게시되어 있는 학생과 다른 경우 게시하고자 하는 학생을 게시하고, 추천 횟수를 초기화하고 시간을 재설정한다.

 

그다음, 추천 횟수를 1 증가시킨다.

 

사진틀의 개수가 최대 20개, 추천 횟수가 1000번 이하이므로 전부 탐색해도 시간 초과가 발생하지 않는다.

 

정렬 후, student의 원소가 0인지 확인한 이유는 문제 조건에 모든 사진틀에 학생이 게시된다는 조건이 없기 때문이다.

 

https://www.acmicpc.net/board/view/71598

글 읽기 - 데이터를 추가해 주세요

 

 

그렇기에, 사진틀에 게시되는 후보의 수가 사진틀의 개수보다 적을 때 에러 처리를 해야 한다.

 

3. 코드

// JAVA 11 , 메모리 : 14456KB, 시간 : 144ms

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int total = 0, now = 0, changeIdx = 0;
        int pictureNum = Integer.parseInt(br.readLine());
        StringTokenizer st;

        int[] student = new int[pictureNum];
        int[] recommend = new int[pictureNum];
        int[] time = new int[pictureNum];

        total = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());

        for (int x = 0; x < total; x++) {

            now = Integer.parseInt(st.nextToken());

            changeIdx = 0;


            for (int y = 0; y < pictureNum; y++) {
               // 사진틀이 비어있거나, 이미 게시된 경우
                if (student[y] == 0 || student[y]==now) {
                    changeIdx = y;
                    break;
                }
                // 추천 횟수가 더 적거나, 추천횟수가 같고 시간이 더 빠른 경우
                if (recommend[changeIdx] > recommend[y] || (recommend[changeIdx] == recommend[y] && time[changeIdx] > time[y])) {
                    changeIdx = y;
                }
            }

            if(student[changeIdx]!=now){
                student[changeIdx] = now;
                recommend[changeIdx] = 0;
                time[changeIdx] = x;
            }

            recommend[changeIdx]++;
        }

        Arrays.sort(student);

        for(int x : student){
            if(x!=0)
                bw.write(String.valueOf(x)+" ");

        }

        bw.flush();
    }



}