백준 23305 - 수강변경 (파이썬)

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

풀이

두 개의 리스트 A와 B가 주어지고, 학생들이 수강 신청을 변경할 때 최소한 몇 명이 원하는 강의를 듣지 못하는지를 구하는 문제이다.

• A : 원래 신청한 강의 목록
• B : 변경 후 원하는 강의 목록

학생들은 강의를 교환할 수도 있지만, 모든 학생이 원하는 강의를 들을 수 없는 경우도 있다.

최대한 많은 학생들이 원하는 강의를 들을 수 있도록 해야 하며, 듣지 못하는 학생 수를 출력한다.

count = {}
for i in range(N) :
    if A[i] not in count :
        count[A[i]] = [0, 0]
    count[A[i]][0] += 1

count라는 딕셔너리를 생성하여 각 강의의 신청 수를 저장한다. not in 을 통해서 딕셔너리에 존재 하지 않는 경우에는 [0, 0] 으로 초기화한다.

만약 딕셔너리에 존재하는 경우에는 신청한 강의의 개수를 증가한다.

B도 동일하지만, B에서 희망하는 강의 개수를 저장한다.

answer = 0
for key, value in count.items() :
    supply = value[0]
    demand = value[1]

    answer += min(supply, demand)

그 후, 각 강의에 대해, 기존에 신청한 학생수와 변경 후 희망하는 학생수를 비교하여, 작은 값만큼 학생들은 강의를 들을 수 있다.

이 값을 answer에 추가한다.

즉, 결국 원하는 강의를 듣지 못하는 학생수는 총 학생수 N에서 원하는 강의를 들을 수 있는 학생수 answer을 빼면, 듣지 못하는 학생수를 출력할 수 있다.

코드

# 백준 23305 - 수강변경
# 분류 : 그리디

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

count = {}
for i in range(N) :
    if A[i] not in count :
        count[A[i]] = [0, 0]
    count[A[i]][0] += 1

for i in range(N) :
    if B[i] not in count :
        count[B[i]] = [0, 0]
    count[B[i]][1] += 1

answer = 0
for key, value in count.items() :
    supply = value[0]
    demand = value[1]

    answer += min(supply, demand)

print(N - answer)