문제

월드초등학교 학생회장 후보는 일정 기간 동안 전체 학생의 추천에 의하여 정해진 수만큼 선정된다. 그래서 학교 홈페이지에 추천받은 학생의 사진을 게시할 수 있는 사진틀을 후보의 수만큼 만들었다. 추천받은 학생의 사진을 사진틀에 게시하고 추천받은 횟수를 표시하는 규칙은 다음과 같다.

학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경우에는 그러한 학생들 중 게시된 지 가장 오래된 사진을 삭제한다.
현재 사진이 게시된 학생이 다른 학생의 추천을 받은 경우에는 추천받은 횟수만 증가시킨다.
사진틀에 게시된 사진이 삭제되는 경우에는 해당 학생이 추천받은 횟수는 0으로 바뀐다.
후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

입력
첫째 줄에는 사진틀의 개수 N이 주어진다. (1≤N≤20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대로 주어진다. 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수이다.

출력
사진틀에 사진이 게재된 최종 후보의 학생 번호를 증가하는 순서대로 출력한다.

링크텍스트

접근

조건에서 따져봐야 할 요소가 많아서 재미있는 문제였다. 한 후보가 가져야하는 중요한 세 변수는 후보 번호, 추천 수, 유지 기간이다. 이러한 변수를 가진 Candi 클래스를 만들어서 활용했다.

N의 크기를 가진 Candi 클래스 배열을 생성하여 조건에 맞게 후보군을 입적시키거나 삭제하는 조건문을 M번(추천 횟수) 반복했다.

조건문의 분기는 크게 두가지로, 이미 후보인 학생이 추천됐을 때/없는 후보일 때, 없는 후보인데 자리가 남지 않았을 때/남았을 때이다.

있는 후보가 추천됐다면 해당 후보의 추천 횟수만 늘려주고, 없는 후보지만 자리가 남았다면 그냥 입적시킨다.

없는 후보인데 자리가 없다면 현재 입적된 후보들을 추천수대로 오름차순, 유지 기간순으로 내림차순 정렬하여 맨 앞으로 정렬된 후보를 갈아치운다.

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	static int can_count, n;
	static Candi [] can;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		can = new Candi[n];
		can_count = 0;
		
		int m = sc.nextInt();
		for(int i = 0; i < m; i++) {
			int tmp = sc.nextInt();
			int idx = can_search(tmp);
			
			if(idx == -1) {
				if(can_count == n) {
					Arrays.sort(can, new Comparator<Candi>() {
						@Override
						public int compare(Candi o1, Candi o2) {
							if(o1.rec == o2.rec)
								return o2.life - o1.life;
							else
								return o1.rec - o2.rec;
						}	
					});
					can[0].num = tmp;
					can[0].rec = 1;
					can[0].life = 0;
				}
				else {
					can[can_count++] = new Candi(tmp);
				}
			}
			else {
				can[idx].rec++;
			}
			
			life_up();
		}
		
		Arrays.sort(can, new Comparator<Candi>() {
			@Override
			public int compare(Candi o1, Candi o2) {
				return o1.num - o2.num;
			}	
		});
		
		for(int i = 0; i < can_count; i++)
			System.out.print(can[i].num + " ");
	}
	
	private static int can_search(int tmp) {
		int idx = -1;
		for(int i = 0; i < can_count; i++) {
			if(can[i].num == tmp)
				idx = i;
		}
		return idx;
	}

	private static void life_up() {
		for(int i = 0; i < can_count; i++)
			can[i].life++;
		
	}

	public static class Candi {
		int num;
		int rec;
		int life;
		
		public Candi(int x) {
			this.num = x;
			this.rec = 1;
			this.life = 0;
		}
	}
}```