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

문제

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

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

후보의 수 즉, 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

예제

풀이 방법

전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보의 학생 번호를 출력하는 문제였습니다.

 

먼저, 후보의 사진을 게시할 수 있는 규칙은

1) N개의 사진틀 중, 비어있는 사진 틀이 존재한다면 학생 사진 게시

2) 비어있는 사진 틀이 존재하지 않는다면

   i) 추천 받은 횟수가 가장 적은 학생 사진 삭제 후 추천 학생 사진 게시

   ii) 추천 받은 횟수가 같으면 게시된 지 가장 오래된 사진 삭제 후 추천 학생 사진 게시

단) 현재 사진이 게시된 학생이 추천을 받은 경우에는 횟수 증가

로 정리할 수 있습니다.

 

게시할 사진의 정보를 저장할 list를 이용하여 만약 list의 사이즈가 N개 보다 적을 경우에는 list안에 추천받은 학생의 정보가 있는지 확인 후, 만약 존재한다면 횟수를 +1 증가시키고, 정보가 없는 경우에는 list에 학생정보를 넣어주었습니다. 만약 비어있는 사진틀이 존재하지 않는다면 마찬가지로 list안에 추천받은 학생의 정보가 있는 경우에는 추천 횟수를 +1 증가시키고, 없는 경우에는 list 맨 앞에 있는 정보를 삭제 후, 추천받은 학생의 정보를 넣어주었습니다.

마지막으로 최종 후보의 학생 번호를 출력하기 위해, list에 들어가있는 학생의 번호를 answer 리스트에 넣어준 뒤, 학생 번호순으로 출력해주었습니다.

 

** 처음에 생각하지 못했던 부분이 비어있는 사진틀이 존재할 경우에 현재 사진이 게시된 학생인지 확인하지 않고 리스트에 넣어줘서 자꾸 틀렸습니다가 떴다.. 앞으로 생각좀하면서 문제풀어야지..

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main_BJ_1713_후보추천하기 {
    
    static class info implements Comparable<info>{
        int index, num, cnt;
 
        public info(int index, int num, int cnt) {
            super();
            this.index = index;
            this.num = num;
            this.cnt = cnt;
        }
 
        @Override
        public int compareTo(info o) {
            if(this.cnt==o.cnt) {
                return this.index-o.index;
            }
            return this.cnt-o.cnt;
        }
        
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        ArrayList<info> list = new ArrayList<>();
        ArrayList<Integer> answer = new ArrayList<>();
        
        int N = Integer.parseInt(br.readLine()); //사진 틀
        int M = Integer.parseInt(br.readLine()); //총 추천 횟수
        
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++) {
            int student = Integer.parseInt(st.nextToken());
            if(list.size()<N) {
                boolean flag = false;
                for(int j=0;j<list.size();j++) {
                    if(list.get(j).num==student) {
                        list.get(j).cnt++;
                        flag = true; break;
                    }
                }
                if(!flag) list.add(new info(i,student,1));
            }
            else {
                Collections.sort(list);
                boolean flag = false;
                for(int j=0;j<list.size();j++) {
                    if(list.get(j).num==student) {
                        list.get(j).cnt++;
                        flag = true;
                        break;
                    }
                }
                if(!flag) {
                    list.remove(0);
                    list.add(new info(i,student,1));
                }
            }
        }
        
        for(int i=0;i<list.size();i++) {
            answer.add(list.get(i).num);
        }
        
        Collections.sort(answer);
        
        for(int i=0;i<answer.size();i++) sb.append(answer.get(i)+" ");
        
        System.out.println(sb.toString());    
    }
 
}