백준 1713번 후보 추천하기

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Candidate_Recommend {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] input = new int[K];
        for (int i = 0; i < K; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        int[] student = new int[101];//추천수
        List<Integer> frame = new ArrayList<>();//학생번호
        for (int i = 0; i < K; i++) {
            if(student[input[i]]==0){
                if(frame.size()<N){
                    frame.add(input[i]);
                    student[input[i]]++;
                }
                else {
                    int min = Integer.MAX_VALUE;
                    int index = 0;
                    int studentnum =0;
                    for (int j = 0; j < frame.size(); j++) {
                        studentnum = frame.get(j);
                        if(min>student[studentnum]){
                            min = student[studentnum];
                            index = j;
                        }
                    }
                    student[frame.get(index)] = 0;
                    student[input[i]]++;
                    frame.remove(index);
                    frame.add(input[i]);

                }
            }else {
                student[input[i]]++;
            }

        }
        Collections.sort(frame, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1,o2);
            }
        });

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < frame.size(); i++) {
            sb.append(frame.get(i)).append(" ");
        }

        System.out.println(sb);
    }
}

문제 조건

1. 비어있는 사진틀이 있다면 무조건 게시
2. 비어있는 사진틀이 없다면 추천받은 횟수가 가장 적은 학생의 사진틀 내리고, 그자리에 게시
3. 추천받은 횟수가 가장 적은 학생이 여러명일땐, 먼저 등록된 학생의 사진 내리고 그자리에 게시
4. 이미 게시된 학생을 추천하면 추천횟수만 증가
5. 사진틀에서 개시를 내리면 학생의 추천횟수 0으로 초기화

풀이 방법

📢이 문제의 핵심은 사진틀 리스트에 게시한 시간 순서대로 저장되어야 한다는 점이다.
삭제한 사진틀 자리에 게시하라고 나와있지만, 마지막에 어차피 오름차순 정렬을 함으로, 그자리에 게시할 필요가 없다.
그리고 시간 순서대로 저장해야, 먼저 등록된 학생을 따로 구할 필요없이 리스트의 앞에서 부터 탐색하기만 하면 된다.
즉, 추천수가 가장 적은 학생들 중 먼저 등록된 학생. 이라는 조건을 따로 처리하지 않고, 자연스럽게 해결할 수 있다.

1. 처음 추천한 학생이라면(사진틀에 없는 학생이라면), 사진틀이 꽉 찼는지 아닌지 확인하고,
   처음 추천한 학생이 아니라면(사진틀에 있는 학생이라면) 해당 학생의 추천수를 증가시킨다.
2. 사진틀이 비어있다면, 사진틀 리스트에 학생번호를 추가하고, 학생의 추천수를 증가시킨다.
3. 사진틀이 꽉차있다면, 사진틀 리스트를 탐색하며 추천수가 가장 작은 학생을 찾고, 그때의 리스트 인덱스를 구한다.
4. 최솟값에 해당하는 학생의 추천수를 0으로 초기화하고, 사진틀 리스트에서 해당 인덱스를 지운다.
5. 새로추천한 리스트를 추가하고, 해당 학생의 추천수를 증가시킨다.
6. 사진틀 리스트를 오름차순 정렬하고 출력한다.

후기

문제의 핵심을 파악하지 못하고, 그자리에 게시해야 한다고만 생각해서 구현하지 못했다.
조건이 여러개일때, 앞에서 부터 탐색하면 자연스럽게 해결되는 조건이 있는지 잘 확인해야겠다.
다음에 다시 풀어봐야겠다.