[BOJ] 1713: 후보 추천하기 (JAVA)

문제

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

 

여담

문제를 읽은 후, HashMap과 우선순위 큐를 사용해야 되겠다고 생각했다. 그치만 중복된 경우를 우선순위 큐에서 어떻게 처리할지 헷갈려서 계속 고민했다. 결국 사진을 삭제할 때만 우선순위 큐를 사용하도록 했고, 다행히 이 방법으로 문제를 풀 수 있었다!

 

풀이

이 문제는 주어진 조건에 따라 단순하게 구현을 하면 되는 문제이다.

 

주어진 조건을 정리하면 다음과 같다.

• 사진틀에 게시될 수 있는 학생의 사진은 최대 N 개
• 비어있는 사진틀이 없는 경우, 아래의 순서에 따라 게시된 사진을 삭제하고 새로운 사진을 게시하기
  1. 추천받은 횟수가 가장 적은 학생의 사진 삭제
  2. 학생들 중 게시된 지 가장 오래된 사진 삭제

학생 정보와 그 학생의 추천 정보(게시 순서, 추천 수)를 저장하기 위해 HashMap을 사용했고, 삭제될 사진을 찾기 위해 우선순위 큐를 사용했다. 

 

문제의 풀이 과정은 다음과 같다.

1. 이미 학생의 사진이 게시된 경우
   
   • HashMap에서 학생의 추천 정보 가져오기
     • Recommend rc = pictures.get(recommendStudent)
   • 가져온 학생의 추천 횟수를 1 증가시켜서 다시 HashMap에 넣기
     • pictures.put(recommendStudent, new Recommend(recommendStudent, rc.idx, rc.cnt + 1))
2. 학생의 사진이 게시되지 않은 경우
   
   • 비어있는 사진틀이 없는 경우라면, 주어진 조건에 따라 삭제할 학생을 찾고 해당 학생의 사진을 삭제하기
     • pictures.remove(removeStudent)
   • 새로운 학생의 사진을 게시하기
     • pictures.put(recommendStudent, new Recommend(recommendStudent, i, 1))
3. 학생의 총 추천 횟수만큼 1번 ~ 2번 과정을 반복하기
4. HashMap에 저장된 학생의 번호를 증가하는 순서대로 출력하기
   • pictures.keySet().stream().sorted().forEach(student -> sb.append(student).append(" "))

 

코드

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

public class Main {
    static int N, M;
    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()); // 전체 학생의 총 추천 횟수
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        HashMap<Integer, Recommend> pictures = new HashMap<>();
        for (int i = 0; i < M; i++) {
            int recommendStudent = Integer.parseInt(st.nextToken());
            if (pictures.containsKey(recommendStudent)) { // 이미 사진이 게시된 경우
                // 그냥 추천 횟수 1 증가해서 넣으면 됨
                Recommend rc = pictures.get(recommendStudent);
                pictures.put(recommendStudent, new Recommend(recommendStudent, rc.idx, rc.cnt + 1));
            } else { // 사진이 게시되지 않은 경우
                // 만약 현재 게시된 사진의 개수가 사진틀의 개수와 같다면, 하나를 빼야 함
                if (pictures.size() == N) {
                    // 우선순위: 추천 횟수가 가장 적은 사진 → 가장 오래 게시된 사진
                    PriorityQueue<Recommend> pq = new PriorityQueue<>();
                    for (int student : pictures.keySet()) {
                        Recommend rc = pictures.get(student);
                        pq.offer(new Recommend(student, rc.idx, rc.cnt));
                    }
                    int removeStudent = pq.poll().student;
                    pictures.remove(removeStudent);
                }
                // 새로운 학생의 사진 게시하기
                pictures.put(recommendStudent, new Recommend(recommendStudent, i, 1));
            }
        }
        StringBuilder sb = new StringBuilder();
        pictures.keySet().stream().sorted().forEach(student -> sb.append(student).append(" "));
        System.out.println(sb.toString());
    }

    static class Recommend implements Comparable<Recommend> {
        int student; // 학생 번호
        int idx; // 게시 순서
        int cnt; // 추천 횟수

        public Recommend(int student, int idx, int cnt) {
            this.student = student;
            this.idx = idx;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Recommend r) {
            // 추천 횟수가 같으면, 가장 오래된 사진 삭제
            if (this.cnt == r.cnt) return this.idx - r.idx;
            return this.cnt - r.cnt; // 그렇지 않으면, 추천 횟수가 제일 적은 학생 삭제
        }
    }
}

---