latentspace.world

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

문제 소개

브실대학은 특정 과목들의 성적 합을 통해 서류 전형의 합격 여부를 결정하는데, 어떤 과목이 반영되는지 일부만 공개한다.

브실이가 얻을 수 있는 최소 점수와 최대 점수를 구하는 문제이다.

문제 조건

수강한 과목 수: N (1 ≤ N ≤ 10,000)
요구하는 과목 수: M (1 ≤ M ≤ N)
공개된 과목 수: K (1 ≤ K ≤ M)
각 과목의 점수: 0 ≤ 점수 ≤ 100
공개된 과목과 비공개된 과목은 모두 브실이가 수강한 과목에 포함되어 있음
과목은 중복되지 않는다.

예시

공개된 과목: physics(50점), python(90점) → 합계 140점
비공개 과목: calculus(100점), probability(70점), chemistry(80점), algorithm(100점)
추가로 필요한 과목 수: 1개
최소 점수: 140 + 70 = 210
최대 점수: 140 + 100 = 240

문제 해법

공개된 K개 과목의 점수를 모두 합산한다. 이는 어차피 반영되어야 하는 점수이기 때문이다.
총 M개 과목을 요구하므로, 추가로 M-K개 과목을 선택해야 한다.
최소 점수를 구하려면, 비공개 과목 중 점수가 가장 낮은 M-K개 과목을 선택한다.
최대 점수를 구하려면, 비공개 과목 중 점수가 가장 높은 M-K개 과목을 선택한다.

최종 구현

이 구현에서 중요한 부분은 비공개 과목이 존재하는 경우에만 비공개 과목 후보 리스트를 정렬, 그 중 필요한 갯수만큼을 뽑는 것이다.

from sys import stdin

input = stdin.readline

def solution():
    N, M, K = map(int, input().split())
    
    # 모든 과목 점수 저장
    courses = {}
    for _ in range(N):
        name, score = input().split()
        courses[name] = int(score)
    
    # 공개된 과목의 점수 합 계산
    revealed_sum = 0
    for _ in range(K):
        name = input().rstrip()
        revealed_sum += courses[name]
        courses.pop(name)  # 딕셔너리에서 해당 과목 제거
    
    # 비공개 과목 수
    additional_needed = M - K
    
    # 비공개 과목이 없는 경우
    if additional_needed <= 0:
        print(revealed_sum, revealed_sum)
        return
    
    # 남은 비공개 과목 점수들만 리스트로 추출
    remaining_scores = list(courses.values())
    
    # 남은 과목 중 비공개 과목 갯수만큼 선택
    remaining_scores.sort()
    min_score = revealed_sum + sum(remaining_scores[:additional_needed])
    max_score = revealed_sum + sum(remaining_scores[-additional_needed:])
    
    print(min_score, max_score)

if __name__ == '__main__':
    solution()

주의 사항 (실수할 수 있는 부분)

리스트 슬라이싱

처음에는 아래와 같이 리스트 슬라이싱을 사용해 최소/최대 점수를 계산했다. (아래 비공개 과목이 없는 경우 예외 처리가 없을 때의 코드)

min_k = sorted_scores[:number_of_unopened_courses]
max_k = sorted_scores[-number_of_unopened_courses:]

print(sum(min_k) + base_score, sum(max_k) + base_score)

만약 number_of_unopened_courses가 0인 경우(모든 과목이 공개된 경우), min_k = sorted_scores[:0]는 빈 리스트를 반환하지만

max_k = sorted_scores[-0:]는 전체 리스트를 반환하는 문제가 있다. 이는 Python에서 [-0:]가 [0:]와 동일하게 동작하기 때문이다.

이 문제를 해결하기 위해 아래 조건을 추가하였다.

추가 과목이 필요 없는 경우의 처리

모든 과목이 공개된 경우(M = K)처럼 추가 과목이 필요 없는 경우는 별도로 처리하는 것이 깔끔하다.

additional_needed = M - K
if additional_needed <= 0:
    print(revealed_scores_sum, revealed_scores_sum)
    return

성능 분석

이 알고리즘의 시간 복잡도는 다음과 같다:

수강한 과목 입력: O(N)
공개 과목 입력: O(K)
비공개 과목 후보 리스트 정렬: O(N log N)
최소/최대 점수 계산: O(M-K)

결과적으로 전체 시간 복잡도는 O(N log N)이다.

공간 복잡도는 모든 과목과 점수를 저장하기 위해 O(N)이 필요하게 된다.