Skip to content

LeetCode -2225. Find Players With Zero or One Losses

개요

player들이 대결을 한 결과정보인 matches가 주어진다.

matches는 [승자, 패자]로 구성되어있는 List형 자료다.

player들은 1보다 큰 숫자로 구분된다.(1,2,3,4 ....) 범위는 0 < player <= 100000

목표

matches가 주어졌을 때, findWinners 함수를 작성하여 answers를 반환해야 한다.

answers는 List로 구성되어 있으며, 구성요소는 아래와 같다.

`answers[0]` : 한 번도 진적이 없는 player

`answers[1]` : 1번 진 player

각 answer의 자료는 오름차순으로 정렬되어야 한다.

출력 예

matches : [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]

answers : [[1,2,10],[4,5,7,8]]

설명 answers[0]:

1은 3에게만 승리하였고, 한번도 진적이 없음. 2는 3에게만 승리하였고, 한번도 진적이 없음. 10은 4에게만 승리하였고, 한번도 진적이 없음.

answers[1]:

4는 5, 8, 9에게 승리하였고 10에게 1패 하였음 5는 6, 7에게 승리하였고, 4에게 1패하였음 7은 한 번도 이긴적이 없고, 5에게 1패하였음 8은 한 번도 이긴적이 없고, 4에게 1패하였음

해결 전략

문제는 0패와 1패한 player를 식별해야 한다.

얼마나 승리를 하였는지는 중요하지 않다고 분석된다.

다만 matches에서 총 몇 명의 player가 게임에 참여하였는지 식별해야 한다.

추가로, answers[0]과 answers[1]은 오름차순으로 정렬되어 있어야 한다.

1. dictionary(map)를 이용한 hash map 사용

  1. key: value 형태로 저장할 수 있는 dictionary(map)을 이용해 matches 안에 참여한 player와 진 횟수를 저장한다.
dictionary = {player:패배_횟수}
  1. 패배 횟수에 따라 오름차순으로 나눠 return한다.
answer = [sorted(find_losses(dictionary,lose=0)),sorted(find_losses(dictionary,lose=1))]

2. List를 이용한 hashtable 사용

List는 순서가 정해저 있는 자료구조이다. 또한, player를 구분하는 자료가 정수이기 때문에 길이가 최대 플레이어 수의 hashtable을 생성한다면 player가 hashtable[player 번호]로 접근했을 때, 바로 접근할 수 있기 때문에 O(1)이 된다.

  1. 최대 플레이어 수 길이의 hashtable을 생성한다.
# -1 = 게임에 참여 안한 player를 구분하는 수이다.
# 들어있는 수는 패배 횟수이다.
hashtable = [-1] * MAX_PLAYERS
  1. 패배 횟수에 따라 return 한다.
# sort할 필요 없이, player 1부터, MAX_PLAYERS까지 조회하면 된다.
answer = [find_losses(hashtable,lose=0), find_losses(hashtable,lose=1)]

회고

hashtable을 사용할 때, dictionary 형태의 자료를 먼저 떠올리곤 했는데

key 값이 integer일 경우엔, 미리 오름차순으로 정렬할 수 있다는 특징을 이용할 수 있음을 알게 되었다.

#coding-interview #hashing

Comments