[백준 - 1713] 후보자 추천 - Java

문제 설명

 

1713번: 후보 추천하기

 

접근 방법

해당 문제는 당초에는 우선순위 큐를 이용하려고 했지만 poll() 또는 remove() 메서드 사용 시 기존에 내부 요소들의 순서가 변동되어 List 자료구조를 이용하여 문제를 해결했습니다.

 

우선 문제에 따르면 "특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다"고 하는데, 이는 기존에 있던 학생의 사진을 빼고 새로운 학생의 사진을 넣어야하는 것을 의미합니다. 이때 기존에 어떤 학생의 사진을 빼냐가 중요한데, 문제에 주어진 추가적인 조건에 따르면 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하되 만일 추천받은 횟수가 가장 적은 학생이 두 명 이상일 경우 가장 오래된 사진을 삭제해야 한다. 즉, 학생의 사진을 빼는데 필요한 조건은 추천받은 횟수와 걸려있는 시간입니다.

 

우선 이를 위해 별도 Student라는 구조체를 만들어 내부 상태로 학생 식별을 위한 id값과 추천받은 횟수, 액자에 걸렸던 시간을 가지도록 했고, Comparable 인터페이스를 구현하여 추천받은 횟수를 기준으로 오름차순으로 정렬하되 동일할 경우 액자에 걸린 시간을 기준으로 오름차순으로 정렬하도록 했습니다.

 

또한 HashMap을 이용하여(containsKey) 학생의 id로 현재 특정 학생의 사진이 액자에 걸려있는지를 확인하도록 했습니다. 만일 기존에 액자에 없는 학생의 사진이라면 새로운 Student 객체를 만들어 List에 넣어준 후 정렬합니다. 이때, 액자에 걸 수 있는 사진의 개수가 가득찬 경우 가장 맨 앞에 있는 학생의 사진이 문제의 조건에 따른 가장 먼저 빼야 할 사진이기 때문에 이를 제거한 후에 새로운 학생의 사진을 넣어줍니다. 기존 액자에 있는 학생의 사진이라면 해당 Student 객체의 추천 횟수를 1 더해주고 다시 정렬하도록 합니다.

 

 

전체 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

class Main {

    static class Student implements Comparable<Student> {
        int id;
        int score;
        int time;

        public Student(int id, int score, int time) {
            this.id = id;
            this.score = score;
            this.time = time;
        }

        @Override
        public int compareTo(Student target) {
            if (this.score == target.score) {
                return this.time - target.time;
            }
            return this.score - target.score;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        Map<Integer, Student> frames = new HashMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        List<Student> list = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            int studentId = Integer.parseInt(st.nextToken());

            if (frames.containsKey(studentId)) {
                frames.get(studentId).score++;
            }
            else {
                if (list.size() == n) {
                    Student s = list.get(0);
                    list.remove(s);
                    frames.remove(s.id);
                }
                Student student = new Student(studentId, 1, i);
                frames.put(studentId, student);
                list.add(student);
            }

            Collections.sort(list);
        }

        List<Integer> result = new ArrayList<>();
        for (Student student : list) {
            result.add(student.id);
        }

        Collections.sort(result);

        StringBuilder sb = new StringBuilder();
        for (Integer integer : result) {
            sb.append(integer).append(" ");
        }

        System.out.println(sb);
    }
}

 

 

참고자료

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