문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
풀이 00
- completion의 길이는 participant의 길이보다 1 작음
- 동명이인 有
- 단 한 명의 완주하지 못한 선수
def solution(participant, completion):
participant.sort()
completion.sort()
for i in range(len(completion)):
if participant[i] != completion[i]:
return participant[i]
return participant[-1]우선, participant와 completion 리스트 내부에 있는 이름을 정렬한다.
이후, 순서가 맞지 않는지 체크를 하여(participant[i] != completion[i]) 맞지 않을 경우, 완주하지 못한 선수로 간주하게 된다!
풀이 01
def solution(participant, completion):
participant.sort()
completion.sort()
for p, c in zip(participant, completion):
if p != c:
return p
return participant[-1]풀이 01은 풀이 00의 연장으로, zip() 내장함수를 사용하여 풀이를 한 것이다.
zip() 함수를 사용하여 두 배열을 묶어주어 간단하게 비교를 하고자 하였으며, zip() 함수는 2개 이상의 리스트를 동일한 인덱스끼리 묶어주는 함수이다. 만약 리스트의 길이가 동일하지 않다면 완성되지 않는 인덱스는 버린다.
풀이 02
def solution(participant, completion):
answer = ''
hash_dict={} # hash dictionary
sumHash=0
for i in participant:
hash_dict[hash(i)]=i # participant hash 인덱스 넣기
sumHash+=hash(i) # hash 총합
for j in completion:
sumHash-=hash(j) # completion의 hash값들 빼기
return hash_dict[sumHash] # 남은 hash값에 해당하는 선수가 완주 못한 선수풀이 02의 경우, 위 풀이들과 달리 문제의 의도에 맞게 hash를 사용한 풀이라고 생각이 든다.
(Hash Map 생성) : Hash Map은 Key-Value의 쌍을 관리하는 클래스로 위 풀이에서는 Key는 Hash값, Value는 선수 이름으로 지정을 했다.
(Hash Map에 Participant 추가) : Hash Map에 Participant를 추가한다.
(sumHash에서 완주한 선수의 hash값 빼주기) : 이후, completion에서의 hash 값들을 빼주게 된다면 마지막으로 남은 hash 값의 value가 완주하지 못한 선수가 된다.
위 풀이에서 사용된 해시(Hash)에 대해서 알아보고자 한다.
- 해시(Hash)
- 해시(Hash)는 해시 테이블(Hash Table)로 Key와 Value를 매핑해서 데이터를 저장하는 자료구조
- 파이썬에서 제공되는 딕셔너리 자료형은 해시 테이블과 같은 구조
키(Key) : 고유의 값, 해시 함수의 Input, 다양한 길이의 값
해시 테이블(Hash Table) / 해시 맵(Hash Map) : Key와 Value를 매핑해서 데이터를 저장하는 자료구조
해시 함수(Hash Function) : 임의의 값을 고정된 길이의 데이터로 변환하는 함수로 다양한 길이의 키를 고정된 길이의 해시로 변환시키므로 저장소를 효율적으로 운영할 수 있음
해시(Hash) : 해시 함수의 Output으로 해시 값과 매칭되어 버킷에 저장됨
해시 값(Hash Value) / 해시 주소(Hash Address) : 키에 해시 함수를 적용하여 얻은 해시 값
버킷(Bucket) : 1개의 데이터를 저장할 수 있는 공간
변환된 키 값과 버킷에 매핑되어 있는 데이터를 해시라고 하며, 이러한 자료구조를 해시 테이블이라고 함
풀이 03
from collections import Counter
def solution(participant, completion):
people_dict = Counter(participant) - Counter(completion)
answer = [*people_dict.keys()][0]
return answercollections.Counter는 컨테이너에 들어있는 요소의 개수를 {'이름' : '개수'} 와 같은 딕셔너리 형태로 반환해준다.
Counter 객체는 뺄셈을 지원한다는 특이점이 존재하며, 이를 활용하여 Counter(participant) - Counter(completion) 완주를 하지 못한 사람들을 딕셔너리 형태로 얻어냈다.
이후, 딕셔너리의 0번째 key의 값을 return한다.
- Dictionary의 Key를 List로 변환하는 방법
tmp = {'a':1, 'b':2}
print(tmp.keys())
>>> dict_keys(['a', 'b'])
# key to list
print([*tmp])
>>> ['a', 'b']
# key to list
print([*tmp.keys()])
>>> ['a', 'b']
# value to list
print([*tmp.values()])
>>> [1, 2]- Counter
- Counter 생성자는 여러 형태의 데이터를 인자로 받음
- 먼저 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체를 얻음
- Counter 생성자에 문자열을 인자로 넘기면 각 문자가 문자열에서 몇 번씩 나타나는지를 알려주는 객체가 반환
collections 모듈의 Counter 클래스는 파이썬의 기본 자료구조인 사전(dictionary)를 확장하고 있으며, if 문에서 in 키워드를 이용하여 특정 키가 카운터에 존재하는지를 확인할 수 있다.
또한, 데이터의 개수가 많은 순으로 정렬된 배열을 리턴하는 most_common()이라는 메서드를 제공하기도 한다.
마지막으로, Counter는 산술 연산자 활용이 가능하여 두 객체를 더하거나 빼는 것이 가능하다. (단, 뺄셈의 결과로 0이나 음수가 나올 경우 최종 카운터 객체에서 제외됨)
참고
