문제 설명
리트코드는 설명보다도 예제를 보면서 이해하는 게 빠르다. 역시나 이 문제도 그렇다.
이 문제는 여러 명이 투표를 해서 랭킹을 정하는 알고리즘을 짜는 문제이다. 처음에 예제를 보고 생각했던 게 Counter를 써서 비교해서 sorting을 해야되나? 싶었는데, 아무튼 바로 풀이 코드 제시하고 설명 간다.
https://leetcode.com/problems/rank-teams-by-votes/description/
풀이 및 설명
class Solution:
def rankTeams(self, votes: List[str]) -> str:
count = {v: [0] * len(votes[0]) + [v] for v in votes[0]}
for vote in votes:
for i, v in enumerate(vote):
count[v][i] -= 1
return ''.join(sorted(votes[0], key=count.get))- count 딕셔너리 구성:
count = {v: [0] * len(votes[0]) + [v] for v in votes[0]}count = {
'A': [0, 0, 0, 'A'],
'B': [0, 0, 0, 'B'],
'C': [0, 0, 0, 'C']
}
- 투표 결과를 바탕으로 count 업데이트
for vote in votes:
for i, v in enumerate(vote):
count[v][i] -= 1왜 -1을 해주냐면, sorted() 함수에서 reverse=True 쓰고 싶지 않아서..
첫 번째 투표 "ABC"
count = {
'A': [-1, 0, 0, 'A'],
'B': [0, -1, 0, 'B'],
'C': [0, 0, -1, 'C']
}
두 번째 투표 "ACB"
count = {
'A': [-2, 0, 0, 'A'],
'B': [0, -1, -1, 'B'],
'C': [0, -1, -1, 'C']
}
세 번째 투표 "ABC"
count = {
'A': [-3, 0, 0, 'A'],
'B': [0, -2, -1, 'B'],
'C': [0, -1, -2, 'C']
}
네 번째 투표 "ACB"
count = {
'A': [-4, 0, 0, 'A'],
'B': [0, -2, -2, 'B'],
'C': [0, -2, -2, 'C']
}
- 팀 정렬:
sorted(votes[0], key=count.get)votes[0]의 각 팀을 count 딕셔너리의 값을 기준으로 정렬.
key=count.get은 각 팀 이름을 count 딕셔너리에서 찾아 반환된 리스트를 정렬의 기준으로 삼음.
votes[0] = 'ABC'
count['A'] = [-4, 0, 0, 'A'],
count['B'] = [0, -2, -2, 'B'],
count['C'] = [0, -2, -2, 'C']
리스트를 비교하여 정렬.
lambda=count.get이 진짜 신박한 함수인 것 같다. 딕셔너리 그 자체를 함수처럼 넣는다는 건 생각도 못해봤는데.. 근데 생각해보면 lambda에는 함수를 넣으면 되는 거니깐 이것도 가능한 거였긴 하다. 아무튼 오늘의 WIL은 딕셔너리 get() 함수!
파이썬 코딩도장: 25.1 딕셔너리 조작하기 <- 여기에서 가져왔다. 딕셔너리에서는 그냥 items() 나 가져올 줄 알았지 여기도 pop, clear, update, setdefault 이런게 있을 줄이야~ 배워간다!
뭐 암튼, 일단 리스트 요소를 넣고 비교하는 전통적인(?) 정렬의 경우에는 리스트의 첫 번째 요소끼리 먼저 비교하고, 만약 같다면 두 번째 요소끼리 비교하고, 등의 연속적인 과정을 거친다.
여기서 포인트는 리스트 요소가 아무리 많아도 자동으로 다음 우선순위를 가지고 비교한다는 거다. count['A'] = [-4, 0, 0, 'A'] 에서 뜬금없이(?) 마지막에 key를 또 넣은 이유도 여기에 있다. vote가 동률이면 사전식으로 정렬하라는 뜻이다.
알고리즘 설명은 끝났고, 앞으로도 sorted는 많이 쓸텐데, 예시를 통해서 어떻게 사용하면 좋은지 리마인드 한 번 하고 가면 좋을 것 같다~
# 참고용
a = [(1, 2), (0, 1), (5, 1), (5, 2), (3, 0)]
b = sorted(a)
# b = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]
c = sorted(a, key = lambda x : x[0])
# c = [(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]
d = sorted(a, key = lambda x : x[1])
# d = [(3, 0), (0, 1), (5, 1), (1, 2), (5, 2)]
e = [(1, 3), (0, 3), (1, 4), (1, 5), (0, 1), (2, 4)]
f = sorted(e, key = lambda x : (x[0], -x[1]))
# f = [(0, 3), (0, 1), (1, 5), (1, 4), (1, 3), (2, 4)]