[LeetCode] 2225. Find Players With Zero or One Losses

2225. Find Players With Zero or One Losses

Medium

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.

 

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

 

Constraints:

• 1 <= matches.length <= 105
• matches[i].length == 2
• 1 <= winneri, loseri <= 105
• winneri != loseri
• All matches[i] are unique.

---

문제 풀이

• 경기에서 이긴 사람과 진 사람이 묶여서 각각 배열에 저장되어 제공된다.
• 첫번째 값은 이긴 사람 두번째 값은 진 사람이다.
• 어느 게임에서도 지지 않은 사람을 정답의 첫번째 배열에 넣고, 최소 한게임에서만 진 사람을 두번째 배열에 넣는다.
• 정답을 리턴할때 오름차순으로 정렬되어 있어야한다.
• 제한사항을 보면 최악의 경우 10^5 가 있기 때문에 브루투포스 O(N^2)로는 풀 수 없다.
• 그렇기 때문에 반복문을 중첩하지 말고 해쉬 맵을 사용하여 저장해서 문제를 풀어야한다.

카운팅 배열 O(N * K)

• 최악의 경우 플레이어의 번호는 10000이다. 
• 이를 이용하여 배열을 미리 선언한다. 
• 초기값을 -1로 해주는 이유는 한번도 지지않은 사람을 가려내야하기 때문이다. 
• 0으로 초기값을 설정한다면 카운팅 배열을 탐색하여 답을 구할때 모든 사람들의 번호를 확인해야 되기 때문이다.
• 즉, 문제에서 주어진 입력값과 상관없는 번호도 한번도 지지않은 사람으로 추가된다.
• 정렬을 사용하지 않고 숫자를 미리 만들어 순서대로 찾기 때문에 이러한 처리가 필요하다.
• 배열의 의미는 게임에서 진 횟수를 의미하고, 진 사람의 횟수를 늘려준다.
• 만약 배열의 값이 초기값이라면 이긴사람은 0으로 진사람은 1로 시작한다.
• 그리고 초기값이 아니면 진 횟수를 늘려준다. 
• 배열을 1부터 최대까지 순서대로 돌리면서 0(한번도 안진), 1(최소 한번만 진)으로 값을 구별하여 정답으로 넣는다. 
• 이렇게 값을 순서대로 넣으면 정렬을 따로하지 않아도 된다.

Sort 정렬 + 해쉬 맵

• 정수 디폴트 딕셔너리를 두개 선언하여 이긴거랑 진것의 개수를 세어준다.
• 이긴 사람들의 딕셔너리를 탐색하면서 이긴 숫자가 0보다 크고 진 딕셔너리의 값이 0이면 답에 한번도 지지 않은 번호를 넣는다.
• 진 사람들의 딕셔너리를 탐색하면서 진 숫자가 1이면 최소 한번만 진 번호를 넣는다.
• 정답을 리턴할때 정렬하여 리턴한다.

소스 코드

카운팅 소트

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        l_cnt = [-1] * 100001
        ans = [[], []]
        for w, l in matches:
            if l_cnt[w] == -1:
                l_cnt[w] = 0
            if l_cnt[l] == -1:
                l_cnt[l] = 1
            else:
                l_cnt[l] += 1
        for i in range(100001):
            if l_cnt[i] == 0:
                ans[0].append(i)
            elif l_cnt[i] == 1:
                ans[1].append(i)
        return ans

 

Sort 정렬 + 해쉬 맵

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        win_d = defaultdict(int)
        lost_d = defaultdict(int)
        w_ans = []
        l_ans = []
        for w, l in matches:
            win_d[w] += 1
            lost_d[l] += 1
        for k, v in win_d.items():
            if v > 0 and lost_d[k] == 0:
                w_ans.append(k)
        for k, v in lost_d.items():
            if v == 1:
                l_ans.append(k)
        return [sorted(w_ans), sorted(l_ans)]