백준 - 2535번 아시아 정보올림피아드 python 문제풀이 [Hellfer]

 

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

2535번: 아시아 정보올림피아드

🔷 알고리즘 분류 - 수학, 정렬   난이도 - 실버 5

collections 모듈의 defaultdict는 파이썬의 내장 딕셔너리(dict)와 비슷한데, 차이점은 키(key)가 존재하지 않을 때 미리 지정해 둔 초기값을 반환한다는 점입니다.

일반적인 딕셔너리에서는 존재하지 않는 키를 호출하면 KeyError가 발생합니다. 

 

하지만 defaultdict를 사용하면, 존재하지 않는 키를 호출해도 미리 설정해 둔 초기값을 반환하여 KeyError를 방지합니다.

기본적인 사용법은 다음과 같습니다.

 

from collections import defaultdict

# 문자열을 선언합니다.
s = 'Hello, World!'

# defaultdict를 선언합니다. 기본값을 int로 설정하면, 키가 없는 경우에는 0을 반환합니다.
char_count = defaultdict(int)

# 문자열의 각 문자를 순회합니다.
for char in s:
    # 현재 문자의 출현 횟수를 1 증가시킵니다. 
    # 이 때, 해당 문자가 처음 나온 경우에는 기본값인 0에서 1을 더하게 됩니다.
    char_count[char] += 1

# 각 문자와 그 출현 횟수를 출력합니다.
print(char_count)

 

위 코드는 입력 문자열 s의 각 문자를 순회하며, 해당 문자가 몇 번 나오는지 char_count라는 defaultdict에 저장합니다. 

 

defaultdict는 키가 없는 경우에는 0을 기본값으로 반환하므로, 특정 문자가 처음 나올 때 KeyError를 발생시키지 않습니다.

코드를 실행하면, 각 문자와 그 출현 횟수를 출력합니다. 출력 결과는 다음과 같습니다.

 

defaultdict(<class 'int'>, {'H': 1, 'e': 1, 'l': 3, 'o': 2, ',': 1, ' ': 1, 'W': 1, 'r': 1, 'd': 1, '!': 1})

🔶문제 풀이 - 그리디 알고리즘을 이용한 풀이

import sys
from collections import defaultdict

# 참가자의 수를 입력받습니다.
n = int(input())
result = []

# 각 참가자의 정보를 입력받아 result 리스트에 저장합니다.
# 이 때, 튜플의 첫 번째 요소를 점수로 설정하여 나중에 점수를 기준으로 정렬할 수 있도록 합니다.
for _ in range(n):
    x, y, z = map(int,input().split())
    result.append((z,x,y)) # z: 점수, x: 학교 번호, y: 학생 번호

# result 리스트를 점수를 기준으로 내림차순 정렬합니다.
result.sort(reverse=True)

# defaultdict를 선언하여 각 학교의 수상자 수를 저장합니다.
winners=defaultdict(int)

# 답을 저장할 리스트를 선언합니다.
answer=[]

# 정렬된 result 리스트를 순회하면서,
for z,x,y in result:
    # 같은 학교에서 두 명 이상 수상하지 않도록 합니다.
    if winners[x]<2:
        winners[x]+=1
        # 수상자의 정보를 answer 리스트에 추가합니다.
        answer.append((x,y))
    # 상위 세 명을 찾았다면 반복을 종료합니다.
    if len(answer)==3:
        break
            
# 수상자의 학교 번호와 학생 번호를 출력합니다.
for i,j in answer:
    print(i,j)

🔶문제 이해하기

아래와 같은 입력값이 주어졌다고 가정해 보겠습니다.

 

9
1 1 230
1 2 210
1 3 205
2 1 100
2 2 150
3 1 175
3 2 190
3 3 180
3 4 195

 

result 리스트를 점수를 기준으로 내림차순 정렬합니다. 

 

[(230, 1, 1) 
(210, 1, 2) 
(205, 1, 3) 
(195, 3, 4) 
(190, 3, 2) 
(180, 3, 3) 
(175, 3, 1) 
(150, 2, 2)
(100, 2, 1)]

 

1. winners 딕셔너리를 생성하여 각 학교의 수상자를 탐색합니다.

 

answer 리스트를 생성하여 수상자의 정보를 저장합니다.

2. 정렬된 result 리스트를 순회하면서, 같은 학교에서 두 명 이상 수상하지 않도록 합니다.

 

이를 위해 winners 딕셔너리를 사용하여 각 학교의 수상자 수를 체크합니다.

 

수상자의 정보를 answer 리스트에 추가합니다.

3. 상위 세 명을 찾으면 반복을 종료합니다.

 

answer 리스트의 길이가 3이 되면 반복을 종료하는 조건을 사용합니다.

4. 수상자의 학교 번호와 학생 번호를 출력합니다.

 

answer 리스트를 순회하면서 각 수상자의 정보를 출력합니다.

5. 최종적으로, 학교 1의 학생 1이 금메달 학생 2가 은메달 그리고 학교 3의 학생 4가 동메달을 수상하는 것을 알 수 있습니다.