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

문제

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

1713번: 후보 추천하기

풀이

문제에서 규칙은 다음과 같았다.

1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
4. 현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
5. 사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.

3번 규칙을 살펴보면, 사진틀이 꽉차면 추천수가 가장 적은 학생의 사진을 삭제한다. 만약, 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.

여기서 우선순위 큐를 생각할 수 있었다. 

 

우선순위 큐는 조건에 따라서 자동으로 정렬해주기때문에 우선순위 큐를 이용하였다. 

조건은 두가지다.

1. 추천수가 같을 경우 오래된것부터 정렬

2. 추천수가 다를 경우 추천수 많은것 부터 정렬

 

구현했을때 다음 순서로 구현했다.

1. 우선순위 큐 내에 같은 학생이 있는지 탐색한다.

2. 있으면 학생의 추천수를 업데이트 해준다. (pq에서 지우고 추천수만 수정해서 다시 넣었다)

3. 큐가 꽉찼을경우(큐의 사이즈가 n일 경우) 같은 학생이 없었다면 지운다.

4. 같은 학생이 없었을 경우 큐에 학생을 넣는다.

 

먼저 우선순위 큐 내에 같은 학생이 있는지 탐색하는 이유는 pq 에 1이 있는 상태에서 1이 들어올경우 1을 넣는게 아니라 1의 추천수를 업데이트 해줘야 되기 때문이다. (이부분을 놓쳐서 틀렸다)

같은 학생이 있었다면 2에서 pq에 반영해주기 때문에 3,4에서는 같은 학생이 없을 경우에 대해서만 고려하면 된다.

코드

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

public class Main {	 

	static class Info implements Comparable<Info>{

		int num;
		int count;
		int time;
		
		public Info(int num, int count, int time) {
			this.num = num;
			this.count = count;
			this.time = time;
		}

		@Override
		public int compareTo(Main.Info o) {
			// TODO Auto-generated method stub
			if(count == o.count)
				return time - o.time;
			else
				return count - o.count;
				
		}
		
	}

	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		int m = Integer.parseInt(br.readLine());
						
		PriorityQueue<Info> pq = new PriorityQueue<>();
				
		int student [] = new int [101];
				
		st = new StringTokenizer(br.readLine());
		
		for(int i=0;i<m;i++) {
			int num = Integer.parseInt(st.nextToken());
			student[num]+=1;
			boolean same = false;
			
			for(Info info : pq) {
				if(info.num == num) {
					pq.add(new Info(num, student[num], info.time));
					pq.remove(info);
					same = true;
					break;
				}
			}
			
			if(pq.size() == n) {
				if(!same) {
					Info info = pq.poll();
					student[info.num] = 0;
				}	
			}
			if(!same)
				pq.add(new Info(num, student[num], i));
		}
		
		int result [] = new int[n];
		
		int idx = 0;
		while (!pq.isEmpty()) {
			result[idx++] = pq.poll().num;
		}
		
		Arrays.sort(result, 0, idx);
		for(int i =0;i<idx;i++) {
			System.out.print(result[i]+" ");
		}
		
	}

	
}