[백준 25391] 특별상 (JAVA)

백준(BOJ) 25391 특별상

 

난이도
230108 기준 골드 5

사용 알고리즘
그리디

문제 링크
https://www.acmicpc.net/problem/25391

25391번: 특별상

 

 

풀이 과정

 

1. 문제 읽기(중요한 부분 굵은 표시)

 

 학생 N명이 미술 대회에 참가하였다. 이 대회에서는 주최자 한 명과 심판 한 명이 수상자를 결정하며, 수상자 결정 방식은 다음과 같다.

1. 주최자와 심판이 각자 모든 학생들의 작품에 점수를 매긴다. 두 사람 모두 점수를 매길 때 서로 다른 두 작품에 같은 점수를 주지 않는다.
2. 주최자가 M명의 학생을 골라 특별상을 수여한다.
3. 심판은 특별상을 받지 않은 학생들이 그린 작품 중 자신이 매긴 점수가 가장 높은 K개의 작품을 추리고, 그에 해당하는 K명의 학생에게 본상을 수여한다.

주최자는 대회에서 종류와 상관 없이 상을 받는 학생들의 작품에 대해 자신이 매긴 점수의 합이 최대가 되도록 하려고 한다. 가능한 합의 최댓값을 구하여라.

 

입력

 첫 번째 줄에 총 학생 수 N, 특별상을 수여할 학생의 수 M, 본상을 수여할 학생의 수 K가 공백으로 구분되어 주어진다. 

두 번째 줄부터 N개의 줄에 걸쳐 각 작품에 대해 주최자가 매긴 점수 ai와 심판이 매긴 점수 bi가 공백으로 구분되어 주어진다. 점수는 모두 정수이다.

 

(세부조건은 블로그에 복사가 이상하게 되어서 중요한 부분만 추리자면 N의 최댓값은 2X10^5이고 ai != aj, bi != bj 를 만족합니다)

 

출력

상을 받는 M+K명의 학생이 그린 작품에 대해 주최자가 매긴 점수의 합의 최댓값을 출력한다.

 

 

2. 어떤 알고리즘을 사용할 것인가

 

 문제 접근법은 그리디로 가면 될 것 같고 N의 크기가 꽤 큰편이니 정렬 할 때 어떤 정렬법을 쓸지를 조금 고민하면 될 것 같네요

 

3. 풀이 구상

 

 문제에서 요구하는 답은 '주최자가 매긴' 점수의 합의 최대값입니다. 심판은 심판 점수가 높은 사람들중에 상위 K명을 무조건 상을 주게 되어있는데요 심판 점수가 높은 K명은 먼저 뽑아 두고 나머지 사람들 중에 주최자 점수가 높은 사람중에 상위 M명을 뽑으면 자연스레 최댓값이 나올 것 입니다.

 문제 풀이법은 알겠는데 N의 크기가 크니 정렬할 때 O(logN)의 시간 복잡도를 갖는 정렬법을 사용해야 겠네요 만만한건 역시 PriorityQueue를 사용한 힙 정렬입니다.

 저는 문제에서 주어진 또 하나의 조건을 한번 의미있게 사용해볼 생각인데요 ai != aj, bi != bj 라는 조건을 보니 각 학생의 host 점수 + " " + judge 점수를 key로 만들면 해쉬맵에서 고유key 값으로 사용할 수도 있겠다는 생각을 했습니다. 시간과 메모리가 조금 더 걸릴 수 있겠지만 한 번 해쉬맵 연습도 해볼겸 써보겠습니다.

 

 일단 심판 점수를 내림차순으로하는 PQ와 주최자 점수를 내림차순으로 하는 PQ 두개를 만들어 값을 다 집어넣어 정렬합니다. 그 후 심판 점수 PQ에서 K명을 뽑아 최종 점수에 합해주면서 HashMap에 위에 말한 key값과 value 1을 집어 넣습니다. 다음에는 while문을 돌리면서 M명의 주최자 픽을 뽑으면 되는데요 주최자 점수가 높은사람이 이미 심판 점수에서 뽑혀있을 수 있으니 HashMap에서 확인을 하고 심판한테 뽑히지 않았으면 뽑는식으로 문제를 풀면 끝날 것 같습니다. 여기까지 구상하고 문제를 풀어보겠습니다.

 

4. 코드 작성

 

1. 정답 코드

import java.io.*;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static class Score{

        long hostScore;
        long judgeScore;

        public Score(long hostScore, long judgeScore) {
            this.hostScore = hostScore;
            this.judgeScore = judgeScore;
        }

        @Override
        public String toString() {
            return "Score{" +
                    "hostScore=" + hostScore +
                    ", judgeScore=" + judgeScore +
                    '}';
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        PriorityQueue<Score> hostpq = new PriorityQueue<Score>(new Comparator<Score>() {
            @Override
            public int compare(Score o1, Score o2) {
                return (int)(o2.hostScore - o1.hostScore);
            }
        });

        PriorityQueue<Score> judgepq = new PriorityQueue<Score>(new Comparator<Score>() {
            @Override
            public int compare(Score o1, Score o2) {
                return (int)(o2.judgeScore - o1.judgeScore);
            }
        });

        for(int i = 1; i <= N; i++){
            st = new StringTokenizer(br.readLine());

            long hostScore = Long.parseLong(st.nextToken());
            long judgeScore = Long.parseLong(st.nextToken());

            Score cur = new Score(hostScore,judgeScore);
            hostpq.add(cur);
            judgepq.add(cur);
        }

        long resultsum = 0;
        HashMap<String,Integer> hm = new HashMap<>();

        for(int i = 1; i <= K; i++){
            Score cur = judgepq.poll();
            resultsum += cur.hostScore;
            String key = cur.hostScore+" "+cur.judgeScore;
            hm.put(key,1);
        }
        int selectedHostCnt = 0;
        while(selectedHostCnt < M){
            Score cur = hostpq.poll();
            String key = cur.hostScore+" "+cur.judgeScore;
            if(!hm.containsKey(key)){
                resultsum += cur.hostScore;
                selectedHostCnt++;
            }
        }

        bw.write(resultsum+"");
        bw.flush();
        bw.close();
        br.close();

    }

}

 

2. 주의할 점

 

 그리디 문제는 항상 내가 생각 못한 예외케이스가 있는지 생각해봐야 합니다. 위 문제는 한 번에 맞췄지만 코드를 작성하기전에 최대한 내 풀이에 대한 예외케이스를 생각해보고 완벽하다 싶을 때 코드를 작성하는게 오히려 시간 절약하는 방법입니다.

 

---

풀이 후기

 이번 주는 프로젝트가 막 시작되는 주라 정신없이 지나갔네요 알고리즘 포스팅을 한 일주일 정도 놨었는데요 짬을 내서라도 올리도록 노력은 해보겠습니다 흑흑