📌문제 설명
📌제한 사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
📌 Solution
이번 문제는 풀다가 정확도 부분에서는 만족을 하였지만 효율성 부분에서 어떻게 시간을 줄여나가야하는지 생각을 제대로 하지 못하였다. 그러하여 구글링을 하여 풀이를 확인하여 보니 총 3가지의 방법이 있었다.
- sort()를 활용
- hash()를 활용
- Collections()의 Counter를 활용
🔍 sort()
def solution(participant, completion):
answer = ''
participant.sort()
completion.sort()
for i, j in zip(participant, completion):
if i!=j:
return i
return participant[-1]
다음과 같이 두 list를 sort를 시키게 되면 같은 인덱스에 정렬이 되어지는데 만약 같지 않은 경우가 발생한다면 완주하지 못한 선수에 해당하므로 바로 return을 시켜준다.
그러나 예외의 경우로 completion의 인덱스를 초과한경우 participant의 마지막 인덱스에 해당하는 선수가 완주하지 못한 선수인 경우가 있으므로 for문 밖에서 예외를 처리하여 줘야한다.
🔍 Hash()
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값에 해당하는 선수가 완주 못한 선수
1.Hash Map 생성
- Hash Map은 Key-Value 쌍을 관리하는 클래스이다.
- 문제에서 Key는 Hash값이고, Value는 선수 이름으로 하였다.
2. Hash Map에 Participant 추가
- Hash Map 에 Participant를 추가한다.
- 아래의 그림과 같은 과정을 거쳐 추가를 한다.
위 그림과 같은 과정을 거치면 표현을 하지 않았지만 남은 B도 해당하는 hash값이 있을 것이다.
3. sumHash에서 완주한 선수의 hash값들 빼주기
위와 같은 과정을 거치게 되면은 completion에서의 hash값들을 빼주게 되면은 마지막으로 남은 hash값의 value가 완주하지 못한 선수가 되어진다!
🔍 Collection.Counter()
from collections import Counter
def solution(participant, completion):
answer = ''
dict_result=Counter(participant)-Counter(completion)
return list(dict_result.keys())[0] Counter라는 아주 획기적인것이 Collection 모듈에 있었는데
간단한 예시를 통해 어떤것인지 알아보자.
예시
li=['kim', 'kim', 'park', 'sung']
diction={}
diction=collections.Counter(li)
# diction={'kim':2, 'park':1, 'sung':1}아래의 코드와 같이 진행할 경우 각각 해당하는 갯수는 value로 list에 있었던 원소들은 key값이 되어진다.
문제를 해결하여질때 핵심은 dict_result=Counter(participant)-Counter(completion)인데 participant의 딕셔너리에서 completion의 딕셔너리를 빼게되면 결론적으로는 남은 participant의 key가 완주하지 못한 선수가 되어진다.
그리하여 list(dict_result.keys())[0]를 return하면 되어진다.
-
dict_result.keys()를 불러오면 해당 딕셔너리의 key값을 리스트로 모두 불러오지만 결과적으로는 하나만 남아있다.
-
그 리스트의 첫번째 인덱스에 있는 값이 완주하지 못한 선수이다.
✨ 문제 해결하며 알게 된 점
-
Hash값을 활용하여 다른 딕셔너리 확인하는 방법
-
Dictionary끼리는 뺄 수 있다는 것
-
Collection모듈의 Counter를 활용하는 방법.
