[2024] Day15. 2225. Find Players With Zero or One Losses

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 15일 (월)
Leetcode daily problem

2225. Find Players With Zero or One Losses

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

Problem

주어진 matchs 배열에서
match[i] = [winner, loss] 각 인덱스의 요소는 각 경기(match)당 승자 플레이어(winner)가 패자 플레이어(loss)를 이겼음을 나타낸다.

경기에 한 번도 지지 않은 플레이어와, 경기에 한 번 진 플레이어를 리스트의 요소로 반환 한다. 각 요소들은 오름차순으로 반환한다.

최소 한 번 이상 경기를 치른 플레이어만 고려해야 한다.

Solution

Data structure, array

Insert: 삽입 연산은 배열에 요소를 추가하고, 동시에 해당 요소를 해시 테이블에 저장한다. 해시 테이블의 키는 요소로, 값은 해당 요소의 인덱스로 저장한다.

Delete: 삭제 연산은 배열에서 해당 요소를 찾아서 제거한다.
배열의 마지막 요소를 삭제한 위치로 옮겨와서 빈 공간을 채운 후에,
pop을 통해서 상수 시간내에 요소를 제거한다.
마지막 요소로 옮겨진 요소의 인덱스를 업데이트하고, 해시 테이블에서도 해당 요소를 제거한다.

GetRandom: random 라이브러리로 random 모듈을 사용해서 무작위로 요소를 가져온다.

Code

class Solution:
    def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
        players = defaultdict()

        for winer,loser in matches:
            players[winer] = 0 + players.get(winer,0)
            players[loser] = 1 + players.get(loser,0)

        zero, one = [], []
        for player, cnt in players.items():
            if cnt ==0:
                zero.append(player)
            if cnt ==1:
                one.append(player)

        return [sorted(zero), sorted(one)]

Complexicity

시간 복잡도

각 matches의 loop는 한 번씩 실행되어 O(n) 시간이 소요된다.
players[winer] 및 players[loser]는 딕셔너리에 접근하고 갱신하는데는 상수시간 O(1) 이 소요된다.
실행하면서 각 이긴 시간 및 진 시간을 기록한 딕셔너리에서는 고유한 플레이어 수에 비례하게 소요된다. O(m)
for player, cnt in players.items(): 루프는 딕셔너리의 크기에 비
따라서 전체 시간 복잡도는 O(n + m) 이다.

공간 복잡도

딕셔너리에서 모든 플레이어에 대한 정보를 저장하므로 O(m) 공간이 필요하고,
zero, one 리스트의 경우 모든 플레이어가 한 번 지거나 아예 지지 않을 경우가 있어서 전체 공간 복잡도는 O(m) 이다.

---