[백준, 자바] 1713번 후보 추천하기, 예외 케이스

1. 문제

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

2. 코드

문제 푸는 것에 지쳐서 설명은 주석으로 대체한다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {

    static int N;
    static int M;

    static int[] persons; // 입력으로 받은 사람 번호
    static Map<Integer, Person> pickPersons; // 사진이 등록된 사람, <사람 번호, 등록 시간 및 추천 개수>
    static int[] pickPersonIdx; // Map은 인덱스로 접근이 안되므로, Map의 key 값을 pickPersonIdx에 저장
    static int pickTime; // 추천된 시간

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 사진 개수
        M = Integer.parseInt(br.readLine()); // 인원수
        persons = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::valueOf)
                .toArray();

        pickPersonIdx = new int[N];
        Arrays.fill(pickPersonIdx, -1);
        pickPersons = new HashMap<>();

        int[] answer = answer();
        StringBuilder sb = new StringBuilder();
        for (int number : answer) {
            if (number != -1) {
                sb.append(number + " ");
            }
        }
        System.out.println(sb);
    }

    static int[] answer() {
        for (int person : persons) {
            if (pickPersons.containsKey(person)) { // 이미 사진에 등록되어 있다면
                pickPersons.get(person).recommendCount++; // 추천수 1 증가
            } else {
                if (pickPersons.size() == N) { // 사진틀이 꽉찬 경우
                    int removePictureIdx = getRemovePictureIdx(); // 삭제할 사람의 번호가 담긴 pickPersonIdx의 인덱스
                    pickPersons.remove(pickPersonIdx[removePictureIdx]); // pickPersonIdx에서 사람 번호를 가져온 후, 사진에서 제거
                    // 사진 게시
                    pickPersonIdx[removePictureIdx] = person; // removePictureIdx : 현재 사람(person)이 등록되기 위해 삭제된 사람의 번호가 담긴 pickPersonIdx의 인덱스
                    pickPersons.put(person, new Person(pickTime++, 0)); // 사진틀에 추가된 사람의 정보 저장
                } else { // 게시할 공간이 있다면
                    // 사진 게시
                    pickPersonIdx[pickPersons.size()] = person;
                    pickPersons.put(person, new Person(pickTime++, 0));
                }
            }
        }

        Arrays.sort(pickPersonIdx);
        return pickPersonIdx;
    }

    static int removePickIdx(int number) {
        for (int i = 0; i < N; i++) {
            if (pickPersonIdx[i] == number) {
                return i;
            }
        }
        return -1;
    }

    static int getRemovePictureIdx() {
        // 1. 추천 받은 수가 가장 적은 학생 삭제
        int minRecommendPersonCount = 0; // 가장 적게 추천받은 인원수
        int minRecommend = Integer.MAX_VALUE; // 가장 적게 추천받은 개수
        int minRecommendPersonNumber = -1; // 가장 적게 추천받은 사람의 번호
        for (int pickIdx = 0; pickIdx < N; pickIdx++) {
            Person person = pickPersons.get(pickPersonIdx[pickIdx]);
            if (minRecommend == person.recommendCount) { // 가장 적게 추천받은 개수가 같다면
                minRecommendPersonCount++;
            } else if (minRecommend > person.recommendCount) { // 가장 적게 추천 받았다면
                minRecommend = person.recommendCount;
                minRecommendPersonCount = 1;
                minRecommendPersonNumber = pickIdx;
            }
        }

        // 2. 가장 적게 추천받은 인원이 2명이상이라면
        if (minRecommendPersonCount >= 2) {
            int removeIdx = -1; // pickPersonIdx 요소
            int enrollOldTime = Integer.MAX_VALUE; // 사진틀에 가장 오래 있었던 사람의 시간 (가장 빨리 등록된 사람이 가장 오래 등록된 것임)
            for (int i = 0; i < N; i++) {
                Person pickPerson = pickPersons.get(pickPersonIdx[i]);
                if (pickPerson.recommendCount == minRecommend) {
                    if (pickPerson.enrollTime < enrollOldTime) {
                        removeIdx = i;
                        enrollOldTime = pickPerson.enrollTime;
                    }
                }
            }
            return removeIdx; // pickPersonIdx[removeIdx]에 접근하여 사람 번호를 얻은 후, Map에서 삭제하면 됨
        }

        return minRecommendPersonNumber; // pickPersonIdx[minRecommendPersonNumber]에 접근하여 사람 번호를 얻은 후, Map에서 삭제하면 됨 
    }

    static class Person {
        int enrollTime; // 등록 시간
        int recommendCount; // 추천 횟수

        public Person(int enrollTime, int recommendCount) {
            this.enrollTime = enrollTime;
            this.recommendCount = recommendCount;
        }
    }
}

 

3. 예외 케이스

https://www.acmicpc.net/board/view/61176