[Programmers][해시(Hash)] 완주하지 못한 선수 python (211028)
문제
코딩테스트 연습 - 완주하지 못한 선수
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수
programmers.co.kr
이해도
★★☆☆☆
소감
- 이름 갯수(1~20개 알파벳 소문자), 동명이인 여부에 낚여서 헤매었다. 이 문제에서는 필요가 없었다.
- 해시를 어떻게 적용해야할지 고민이 되어서 쉬운 문제인데도 접근이 어려웠다.
- 인덱스를 비교해도 되고, 해시맵을 사용해도 된다.
방법 1. 반복문 돌며 인덱스 비교하기
두 리스트의 인덱스를 비교해서 해당 값이 다르면 완주를 못한 사람임을 알 수 있다.
먼저 인덱스를 비교하기 위해 각 리스트를 정렬해야 한다.
원본 리스트는 필요 없으므로 sorted 메서드를 사용한다.
이후 완주자 수(참가자 수 -1) 만큼을 돌면서 인덱스를 비교한다.
다르면 미완주니까 참가자수에서 해당 인덱스를 반환하고,
다 돌았으면 마지막 참가자만 남기 때문에 리스트 마지막 값을 반환한다.
# 1. 두 리스트를 sorting 한다.
# 2. completion list의 length만큼 돌면서, participant에만 존재하는 한명을 찾는다.
# 3. 다 돌아도 답이 없으면 마지막 참가자가 미완주자가 된다.
def solution(participant, completion):
# 인덱스 비교 위해 정렬
participant.sort()
completion.sort()
# 완주자 수(참가자 수-1) 만큼 돌면서 인덱스 비교, 다르면 미완주
for i in range(len(completion)):
if participant[i] != completion[i]:
return participant[i]
# 다 돌았으면 마지막 참가자가 미완주
return participant[-1]
방법 2. 해시맵 사용하기
딕셔너리 형태로 해시맵을 만들면 key에 해시값이, value에 선수들 이름이 들어간다.
이때 참가자들로 만든 해시맵 key값을 모두 합친 값을 구한다.
그 값에서 완주자를 다 돌면서 key값을 모두 빼주면,
남은 값이 곳 완주하지 못한 선수의 hash 값이 된다.
# 1. participant list의 hash를 구하고, hash 값을 더한다.
# 2. completion list의 해시를 빼준다.
# 3. 남은 값이 완주하지 못한 선수의 hash 값이 된다.
# 해시맵(딕셔너리)
def solution(participant, completion):
# 해쉬 넣을 딕셔너리 만든다.
hashDict = {}
sumHash = 0
# participant 의 해시를 구하고, 해시맵(딕셔너리)에 더한다.
for part in participant:
hashDict[hash(part)] = part
# 해시의 합을 더한다.
sumHash += hash(part)
# completion 을 돌면서 해시값을 뺀다.
for comp in completion:
sumHash -= hash(comp)
# 남은 값이 곧 완주하지 못한 선수의 hash 값이므로 딕셔너리에서 찾아 반환한다.
answer = hashDict[sumHash]
return answer방법 3. Counter 클래스를 활용하기
"a dict subclass for counting hashable objects." collections 모듈 내의 counter 클래스.
리스트를 딕셔너리로 변환 후 반환해준다.
a = Counter() # a new, empty counter
b = Counter('gallahad') # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2}) # a new counter from a mapping
d = Counter(cats=4, dogs=8) # a new counter from keyword args
>>> Counter()
>>> Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})
>>> Counter({'red': 4, 'blue': 2})
>>> Counter({'dogs': 8, 'cats': 4})
# 1. participant의 counter를 구한다.
# 2. completion의 counter를 구한다.
# 3. 둘의 차를 구하고, key를 읽어온다.
from collections import Counter
def solution(participant, completion):
part_counter = Counter(participant)
comp_counter = Counter(completion)
remain = (part_counter - comp_counter) # >>> Counter({'leo': 1})
# print(remain.keys()) >>> dict_keys(['leo'])
# print(list(remain.keys())) >>> ['leo']
return list(remain.keys())[0]
보다 간단하게
from collections import Counter
def solution(participant, completion):
answer = Counter(participant) - Counter(completion)
return list(answer.keys())[0]