[백준] 1713번 : 후보 추천하기 (JAVA/자바)

[문제 링크]

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

문제 설명

N개의 사진틀에 추천받은 학생회장 후보 사진을 아래 규칙을 따라 게시할 때, 최종 후보들의 번호를 출력한다.

 

1. 추천받은 순서대로 사진을 사진틀에 게시한다.

2. N개의 사진틀 중 비어있는 사진틀이 없는 경우

   2-1. 새롭게 추천받은 학생이 현재 게시된 학생에 포함된 경우, 해당 학생의 추천 횟수 + 1

   2-2. 새롭게 추천받은 학생이 현재 게시된 학생에 포함되지 않은 경우,

        - 현재까지 추천 받은 횟수가 가장 적은 학생 삭제 + 삭제한 자리에 새로운 학생 게시

        - 추천 받은 횟수가 가장 적은 학생이 2명 이상일 경우, 가장 오래된 학생 삭제

 

 

 

문제 풀이

알고리즘 분류

• 구현
• HashMap(LinkedHashMap)

문제를 읽고 이전에 풀었던 완주하지 못한 선수가 떠올랐다. HashMap의 getOrDefault() 함수를 사용해서 key값의 개수를 센다.

 

하지만 이 문제에서는 추천받은 "순서"가 중요하기 때문에 요소가 삽입된 순서대로 저장되는 LinkedHashMap을 사용해서 문제를 풀었다.

(학생 번호, 추천 횟수)쌍으로 값을 저장하고, getOrDefault() 함수를 사용해서 해당 key 값이 존재하면 value + 1, 존재하지 않으면 새로운 쌍을 생성해서 hashmap에 추가한다.

 

비어있는 사진틀이 없는 경우, 먼저 새롭게 추천 받은 학생(new 학생)이 현재 게시되어 있는지 확인한다.

게시되어 있지 않으면 현재 게시된 학생들 중에서 추천횟수가 가장 적은 한 명을 찾아서 삭제하고 new 학생을 게시한다.

이미 게시되어 있으면 해당 학생의 추천 횟수 + 1

if(hm.size() == n && !hm.containsKey(students[i])) {
    int minKey = 0;
    int minValue = 1001;
    //현재까지 추천횟수가 가장 적은 학생 탐색
    for(Integer key : hm.keySet()) {
        if (minValue > hm.get(key)) {
            minValue = hm.get(key);
            minKey = key;
        }
    }
    hm.remove(minKey);  //추천횟수가 가장 적은 학생 삭제
}

 

전체코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedHashMap<Integer, Integer> hm = new LinkedHashMap<>();

        int n = Integer.parseInt(br.readLine());    //사진틀의 개수
        int m = Integer.parseInt(br.readLine());    //전체 학생 추천 횟수

        int[] students = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        for(int i = 0; i < students.length; i++) {
            if(hm.size() == n && !hm.containsKey(students[i])) {
                int minKey = 0;
                int minValue = 1001;
                //현재까지 추천횟수가 가장 적은 학생 탐색
                for(Integer key : hm.keySet()) {
                    if (minValue > hm.get(key)) {
                        minValue = hm.get(key);
                        minKey = key;
                    }
                }
                hm.remove(minKey);  //추천횟수가 가장 적은 학생 삭제
            }

            hm.put(students[i], hm.getOrDefault(students[i], 0) + 1);
        }

        Object[] array = hm.keySet().toArray();
        Arrays.sort(array);

        for (Object o : array) {
            System.out.print(o + " ");
        }
    }
}