https://www.acmicpc.net/problem/12760
문제를 풀면서 몰랐던 개념
(1) [Python] 비어있는 배열, 리스트 확인하기
-> 리스트가 비어있는지 아닌지 여부를 확인하기 위해서는 'not'을 사용해서 알 수 있음!
# case 1 #
arr = []
if not arr:
print("arr is empty")
else:
print("arr is not empty")
# 출력결과
>>> arr is empty
# case 2 #
arr = [2,4,5]
if not arr:
print("arr is empty")
else:
print("arr is not empty")
# 출력결과
>>> arr is not empty
-> 리스트의 길이를 통해서도 확인할 수 있음!
arr = []
if len(arr) == 0:
print("arr is empty")
else:
print("arr is not empty")
# 출력결과
>>> arr is empty
(2) [Python] 리스트 중복 요소 개수 카운팅하기
-> try,except문 사용하기
: for문을 통해 리스트 arr의 요소를 하나씩 꺼내서 count라는 이름의 딕셔너리에 넣는다. 이 때, 딕셔너리 count에 이미 존재하는 키 값이라면, try문이 실행되어 value에 +1을 하게 되고 새로운 키 값이라면 1을 넣기
count = {}
arr = [ "one2ye","20s","20s","love","love","love" ]
for i in arr:
try: count[i] += 1
except: count[i] = 1
print(count)
# 출력결과
>>> {'one2ye': 1, '20s': 2, 'love': 3}
(3) [Python] 딕셔너리 내부에서 value가 가장 큰 것 찾기
-> 가장 큰 value값을 가진 키를 출력하는 방법
my_dict = {'one2ye': 1, '20s': 2, 'love': 3}
max_key = max(dict, key = dict.get)
print(max_key)
# 출력결과
>>> love
(4) [Python] 딕셔너리에서 같은 최댓값을 가진 여러개의 값들의 key값을 출력하기
-> 최댓값(value의 값)을 가진 원소들이 여러개일 때 그 요소들의 key값들을 모두 출력하는 방법!
my_dict = {'one2ye': 1, '20s': 2, 'love': 3, 'happiness':3}
maxNum = max(my_dict.values())
d = dict((key,value) for key,value in my_dict.items() if value == maxNum)
print(*d)
# 출력결과
>>> love happiness
문제의 접근 방법
- 입력 받은 각 카드들을 내림차순으로 정렬하기
- 플레이어들이 점수를 얻은 횟수를 저장할 배열 선언하기 (초기값 0)
- 가장 많은 점수를 획득한 플레이어가 여러 명일 수 있기 때문에 획득한 점수의 최댓값과 각 플레이어들이 획득한 점수들을 비교하기
내가 막혔던 부분
모든 플레이어들의 수가 가장 큰 카드들을 비교한 후 몇 번 플레이어가 가장 많은 점수를 획득했는지 판별하는 방법
내가 생각했던 문제 풀이 방법 (오답)
n,m = map(int, input().split())
arr = []
for _ in range(n): # 카드 m개를 n명의 플레이어 수 만큼 입력 받기
cardNum = sorted(list(map(int, input().split())), reverse=True) # 내림차순 정렬
arr.append(cardNum) # 정렬한 cardNum을 arr에 추가
final = []
while True:
if len(arr[0]) == 0: # while 루프를 빠져나가기 위해 arr[0]의 길이가 0이면 break
del[arr]
break
result = []
for i in range(len(arr)):
result.append(arr[i][0]) # arr[i][0]값들을 result에 추가(각 배열의 최댓값)
del arr[i][0] # 한번 사용된 카드는 버리므로 삭제하기
maxNum = max(result) # result에 저장된 값들 중 최댓값을 maxNum에 저장
j = 1 # 가장 큰 수를 가진 플레이어들이 여러명일 경우를 대비해서 비교하기
for j in range(1, len(result)+1):
if result[j-1] == maxNum: # result의 j-1번째 요소부터 비교해서 maxNum과 같다면
final.append(j) # 그 값의 인덱스 j를 final에 저장하기
count = {} # 딕셔너리 count 선언
for k in final: # 위의 과정에 걸쳐 점수를 획득한 플레이어들의 번호가 나열돼있는 final안에서
try: count[k] += 1 # 그 값이 있다면 1을 누적해서 더하고
except: count[k] = 1 # 없다면 1을 추가하기 (딕셔너리의 키와 값)
# 각 플레이어의 번호가 총 몇 번이 나왔는지 세는 것 = 각 플레이어 별 획득한 점수의 합
max_key = max(count.values()) # 딕셔너리 count의 밸류값들 중 최댓값을 찾아 max_key에 저장
d = dict((key, value) for key, value in count.items() if value == max_key)
# count에 저장돼있는 키와 밸류 값들 중 value가 위에서 구한 최댓값과 같다면
[ print(k, end=' ') for k in d ] # 그 인덱스 번호를 출력하기(가장 많은 점수를 획득한 플레이어들의 번호)
소스코드 (정답)
n,m = map(int, input().split())
arr = []
for _ in range(n): # 카드 m개를 n명의 플레이어 수 만큼 입력 받기
cardNum = sorted(list(map(int, input().split())), reverse=True) # 내림차순 정렬
arr.append(cardNum) # 정렬한 cardNum을 arr에 추가
card = n * [0] # 플레이어 수 만큼 크기의 배열 생성(현재 값들은 0)
for i in range(m):
maxNum = arr[0][i] # arr[0][i] 번째 요소를 m에 저장
for j in range(n):
maxNum = max(maxNum, arr[j][i]) # m과 arr[j][i]번째 값을 계속 비교해서 최댓값을 m에 저장
for j in range(n):
if arr[j][i] == maxNum: # 만약 arr[j][i]번째 값이 m과 같다면
card[j] += 1 # 미리 선언해 둔 card의 j번째에 1을 누적해서 더하기
result = [] # 가장 많은 점수를 획득한 플레이어들이 여러명일 때 모두 출력하기 위한 과정
for i in range(len(card)): # 각 플레이어들이 획득한 점수들이 모여있는 리스트 card
if max(card) == card[i]: # card의 최댓값이 card[i]번째 원소와 같으면 그 인덱스를 result에 저장
result.append(i+1) # 인덱스는 0부터 시작이므로 +1해서 저장
print(*result) # result 리스트의 원소들을 출력
'백준 write-up > 정렬 & 그리디' 카테고리의 다른 글
[백준] 종이자르기 : 2628번 - Python (0) | 2022.06.18 |
---|---|
[백준] 세수정렬 : 2752번 - Python (0) | 2022.06.17 |
[백준] 잃어버린 괄호 : 1541번 - Python (0) | 2022.06.14 |
[백준] 거스름돈 : 5585번 - Python (0) | 2022.06.13 |
[백준] 사탕 : 11256번 - Python (0) | 2022.06.12 |