2225. Find Players With Zero or One Losses

문제

You are given an integer array matches where matches[i] = [winneri, loseri] indicates that the player winneri defeated player loseri in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.
The values in the two lists should be returned in increasing order.

Note:

You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.

https://leetcode.com/problems/find-players-with-zero-or-one-losses/

접근

#해시테이블 #sort

구하고 싶은 값은 '패배 수'에 달려 있기 때문에, defaultdict를 통해 패배한 수를 카운트하면 되겠다는 생각이 들었다. 하지만 이것은 한 번이라도 패배한 플레이어의 수만을 체크하고, 단 한번도 패배하지 않은 사람은 딕셔너리에 추가되지 않았다.

이 문제를 해결하기 위해 플레이어 전원을 카운트하는 seen을 선언하였다. set을 사용해 중복된 값을 지우면 결과적으로 모든 플레이어를 담은 집합이 된다.

이제 이 seen을 순회하며, 각 플레이어의 lose내용을 검색한다. 저장되지 않은 플레이어는 defaultdict의 성질에 따라 0값을 리턴받는다.

코드

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        lose = collections.defaultdict(int)
        seen = set()
        
        for m in matches:
            lose[m[1]] += 1
            seen.add(m[0])
            seen.add(m[1]) # member 추가
        
        lose_one, lose_zero = [], []
        
        for s in seen:
            count = lose[s]
            if count == 0:
                lose_zero.append(s)
            elif count == 1:
                lose_one.append(s)
                
        
        return [sorted(lose_zero), sorted(lose_one)]

효율성

Runtime: 4970 ms, faster than 17.58% of Python3 online submissions for Find Players With Zero or One Losses.
Memory Usage: 70.2 MB, less than 11.26% of Python3 online submissions for Find Players With Zero or One Losses.