문제

BOJ 1713: 후보 추천하기 https://www.acmicpc.net/problem/1713

풀이

• 문제에 적혀 있는 조건 그대로 구현하면 된다.
  
  
  
• LinkedList 를 사용하여 액자를 구현한다.
• Stack 을 사용하여 추천수(cnt) 가 같은 후보들의 추천 받은 시간(time) 을 구분한다.
  
  
  
• 새로운 후보(vote)를 받을 때 빈 액자가 있는 지 구분한다.
  • 빈 액자가 있을 때
    • 새로운 후보(vote)가 이미 추천을 받은 후보일 때
    • 새로운 후보(vote)가 새로운 후보일 때
  • 빈 액자가 없을 때
    • 새로운 후보(vote)가 이미 추천을 받은 후보일 때
    • 새로운 후보(vote)가 새로운 후보일 때
      • list 에 있는 후보들 중 추천수(cnt) 가 가장 작은 사람 자리에 새로운 후보(vote)를 넣는다.
      • 만약 여기서 추천수(cnt) 가 가장 작은 사람이 2명 이상이라면
        • 추천 받은 시간(time) 이 가장 작은(가장 오래된) 사람 자리에 새로운 후보(vote)를 넣는다.

코드

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); // 액자 수
		int M = Integer.parseInt(br.readLine()); // 추천 받는 수
		
		LinkedList<Vote> list = new LinkedList<>();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int time = 0;
		for(int m=1; m<=M; m++) {
			int vote = Integer.parseInt(st.nextToken());
			
			// 빈 액자가 있다면?
			boolean isIn = false;
			if(list.size() < N) {
				// 추천 받은 사람이 이미 액자에 있다면? -> 그 사람의 추천수를 +1
				for(int i=0; i<list.size(); i++) {
					if(list.get(i).num == vote) {
						Vote v = list.get(i);
						list.remove(i);
						list.add(new Vote(v.num, v.cnt + 1, v.time));
						isIn = true;
						break;
					}
				}
				// 추천 받은 사람이 액자에 없는 새로운 사람이라면? -> 빈 액자에 넣음
				if(!isIn) {
					list.add(new Vote(vote, 1, time));
				}
				
			} else {// 이미 액자가 모두 차있다면?
				// 추천받은 사람이 이미 액자에 있는 사람이라면?
				boolean isInIt = false;
				for(int i=0; i<list.size(); i++) {
					if(list.get(i).num == vote) {
						Vote v = list.get(i);
						list.remove(i);
						list.add(new Vote(v.num, v.cnt + 1, v.time));
						isInIt = true;
						break;
					}
				}
				
				// 추천받은 사람이 액자에 없는 새로운 사람이라면?
				int minVote = Integer.MAX_VALUE;
				int minVoteIdx = 0;// 추천을 가장 적게 받은 사람
				Stack<Vote> stack = new Stack<>(); // 가장 작은 추천수와 같은 추천수를 가진 사람의 인덱스를 넣을
				if(!isInIt) {
					// 가장 추천수가 적은 자리에 새로운 사람을 넣는다
					for(int i=0; i<list.size(); i++) { // 가장 작은 추천수 구하기
						int voteCnt = list.get(i).cnt;
						if(minVote > voteCnt) {
							minVote = voteCnt;
							minVoteIdx = i;
						}
					}
					for(int i=0; i<list.size(); i++) { // 가장 작은 추천수와 같은 추천수를 받은 사람의 수
						if(list.get(i).cnt == minVote) {
							Vote v = list.get(i);
							stack.add(v);
						}
					}
					
					int minTime = Integer.MAX_VALUE;
					int minTimeNum = 0;// 가장 오래된 사람 찾기
					if(stack.size() == 1) { // 가장 작은 추천수를 가진 사람이 한 명 이라면??
						list.remove(minVoteIdx); // 가장 작은 추천수를 가진 사람 제거
						list.add(new Vote(vote, 1, time)); // 그 후 새로운 사람 추가
					} else { // 가장 작은 추천수를 가진 사람이 여러명이라면 가장 오래 된 사람 자리에 넣는다
						int minTimeNumIdx = -1;
						while(!stack.isEmpty()) { // 스택이 모두 빌 때 까지 반복
							
							Vote v = stack.pop();
							int popTime = v.time;
							if(popTime < minTime) {
								minTime = popTime;
								minTimeNum = v.num;
							}
							
							minTimeNumIdx = 0;// 해당 숫자를 통해 list에 있는 인덱스를 찾는다
							for(int i=0; i<list.size(); i++) {
								if(list.get(i).num == minTimeNum) {
									minTimeNumIdx = i;
								}
							}
							
						}
						list.remove(minTimeNumIdx);
						list.add(new Vote(vote, 1, time));
					}
					
				}
				
			}
				
			time++;	
		}
		
		StringBuilder sb = new StringBuilder();
        // list에 있는 후보 이름(num) 만 출력하기 위해 새로운 배열을 만든다
		int[] arr = new int[list.size()];
		for(int i=0; i<list.size(); i++) {
			arr[i] = list.get(i).num;
		}
		
		Arrays.sort(arr);
		
		for(int i=0; i<arr.length; i++) {
			sb.append(arr[i]).append(" ");
		}
		
		System.out.println(sb);
	}
	
	static class Vote{
		int num, cnt, time;
		
		Vote(int num, int cnt, int time){
			this.num = num;
			this.cnt = cnt;
			this.time = time;
		}
	}

}

정리

• 가장 적은 추천수를 받은 사람이 2명 이상일 때 그 사람들 중 시간이 가장 오래 된 사람을 빼고 새로운 사람을 추가해야하는데 이 부분에서 코드를 잘 못 작성하여 시간 낭비를 했다.
• 마지막에 배열 arr 을 만들거나 출력할 때 list.size() 가 아닌 N 을 사용하여 java.lang.IndexOutOfBoundsException이 발생하였다.
• LinkedList와 Stack 을 사용하여 쉽게 해결할 수 있었다.