오늘의 문제...
📍 완주하지 못한 선수
Q. 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
<제한사항>
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
풀이
처음에는 단순히 차집합 문제라고 생각했다. participant와 completion 배열을 집합으로 변환해서 차집합을 구한 뒤 그 요소를 추출하는 방식으로 접근하려고 하였다. 그 풀이는 다음과 같다.
def solution(participant, completion):
answer = set(participant)-set(completion) # 차집합 연산
answer = answer.pop() if answer else '' # 집합 원소를 추출
return f"{answer}" # " "형태로 변환하지만 위 코드는 '참가자 중에는 동명이인이 있을 수 있습니다' 라는 제한사항을 충족하지 못하기 때문에 답이 될 수 없다.
집합은 리스트와 달리 중복을 인식하지 않으므로 동명이인을 구분하지 못하기 때문이다.
이를 해결하기 위한 방법으로는 collections 모듈에서 제공하는 파이썬 내장함수 Counter를 사용하는 방법이 있다.
collections.Counter함수는 중복된 데이터가 포함된 배열을 인자로 넘기면 각각의 원소가 몇 번씩 나오는지를 딕셔너리 형태로 반환해준다. 다음은 사용 예시이다.
Counter(["a", "b", "c", "c", "c", "a"])
>>> Counter({'a': 2, 'b': 1, 'c': 3})
Counter("hello world")
>>> Counter({'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1})Counter함수는 기본 연산(+, -, &, |)이 가능하다는 특징이 있다. - 연산을 활용해서 본 문제를 해결한 코드는 아래와 같다.
from collections import Counter
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
# Counter함수는 뺄셈이 가능
answer = list(answer.keys())[0]
# answer의 키값을 리스트로 변환해 추출
return answer참고할 만한 다른 풀이
다만 이 문제는 '해시'카테고리에 속해 있다. 해시는 무엇인지 다른 풀이를 참고해서 정리해보자.
def solution(participant, completion):
answer = ''
temp = 0
dic = {}
for part in participant:
dic[hash(part)] = part # participant에 해시값 부여
temp += int(hash(part)) # 부여된 해시값을 모두 더해줌
for com in completion:
temp -= hash(com) # completion 해시값을 빼줌
answer = dic[temp] # 딕셔너리 형태로 반환
return answer새롭게 알게 된 것
- hash() : 객체의 해시 값(정수)를 반환(각 값에 대한 고유한 숫자를 부여)
hash()를 사용하면 각 선수의 고유 숫자가 key이고, 선수명이 value인 딕셔너리가 반환된다. 따라서 participant의 hash값을 모두 temp에 더해준 뒤, completetion의 hash값을 빼준다. 연산된 temp를 dic의 key로 불러와 answer에 담아주고 반환하면 완주하지 못한 선수가 나오게 된다.
