[99클럽 코테스터디 TIL 18일차] 백준 29723번 브실이의 입시전략 해설 및 풀이 (Java)

 

백준 29723번 브실이의 입시전략

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

 

---

문제

올해 고3인 브실이는 세계 최고의 명문 대학 브실대학(브론즈실버대학)에 가기 위해서 자신의 현재 점수를 토대로 입시 전략을 세우려고 한다. 브실대학에서는 특정 과목들의 성적의 합을 통해 서류 전형의 합격여부를 결정한다고 한다. 그러나 브실대학에서는 어떤 과목이 서류 평가에 반영되는지 모두 알려주지 않고 일부만 알려주는 사악한 학교다. 브실대학에서 요구하는 과목 수와 반영된다고 공개된 과목들이 주어질 때, 브실이가 얻을 수 있는 최소 점수와 최대 점수를 구해보자.

단, 공개된 과목과 비공개된 과목은 브실이가 수강한 과목에 모두 포함되어 있으며, 과목은 중복되지 않는다.

입력

첫 번째 줄에 브실이가 수강한 과목 수 N과 브실대학에서 요구하는 과목 수 M, 그리고 브실대학에서 공개한 과목 수 K가 공백으로 구분되어 주어진다. (1≤K≤M≤N≤10000) 

그다음 N줄에 걸쳐 브실이가 수강한 과목 이름 si과 정수 점수 pi가 공백으로 구분되어 주어진다. si는 영어 소문자로만 이루어져 있다. (3≤|si|≤20; 0≤pi≤100)

그다음 K줄에 걸쳐 브실대학에서 공개한 과목 이름 ti가 주어진다. ti는 영어 소문자로만 이루어져 있다. (3≤|ti|≤20)

출력

브실이가 얻을 수 있는 최소 점수와 최대 점수를 공백으로 구분하여 출력한다.

 

---

문제 유형

자료 구조

정렬

해시를 사용한 집합과 맵

 

풀이 방법 도출

1. 모든 과목과 점수를 Map에 저장합니다.
2. 공개 과목은 Set에 저장하고 점수를 minScore, maxScore에 무조건 더합니다.
3. 비공개 과목의 점수들만 리스트에 따로 모은 후 정렬합니다.
4. 최소 점수는 비공개 과목 중에서 점수가 낮은 순서대로 (M - K)개입니다.
5. 최대 점수는 비공개 과목 중에서 점수가 높은 순서대로 (M - K)개입니다.
6. 각각을 minScore, maxScore에 추가합니다.

 

 

시간 복잡도

• 입력 : O(N)
• 정렬 : O(N log N)
• 총 시간 복잡도 : O(N + K + N log N)

---

핵심 코드 삽입 및 설명

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

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

        // N: 수강한 과목 수
        // M: 요구 과목 수
        // K: 공개된 과목 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Map<String, Integer> subjectScores = new HashMap<>();
        Set<String> publicSubjects = new HashSet<>();

        // 과목과 점수 저장
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String subject = st.nextToken();
            int score = Integer.parseInt(st.nextToken());
            subjectScores.put(subject, score);
        }

        // 공개 과목 저장
        for (int i = 0; i < K; i++) {
            publicSubjects.add(br.readLine());
        }

        int minScore = 0;
        int maxScore = 0;

        List<Integer> privateScores = new ArrayList<>();

        for (Map.Entry<String, Integer> entry : subjectScores.entrySet()) {
            String subject = entry.getKey();
            int score = entry.getValue();

            if (publicSubjects.contains(subject)) {
                // 공개 과목은 무조건 포함
                minScore += score;
                maxScore += score;
            } else {
                // 비공개 과목 점수는 리스트에 저장
                privateScores.add(score);
            }
        }

        // 비공개 과목에서 (M - K)개 선택
        Collections.sort(privateScores); // 정렬

        int selectCount = M - K;

        // 최소 점수는 낮은 점수부터 선택
        for (int i = 0; i < selectCount; i++) {
            minScore += privateScores.get(i);
        }

        // 최대 점수는 높은 점수부터 선택
        for (int i = 0; i < selectCount; i++) {
            maxScore += privateScores.get(privateScores.size() - 1 - i);
        }

        System.out.println(minScore + " " + maxScore);
    }
}