해시_PRO#42576 : 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

---

내 코드

def solution(participant, completion):
    answer = participant.copy()
    
    for man in participant:
        if man in completion:
            completion.remove(man)
            answer.remove(man)
    return answer[0]

효율성에서 합격하지 못했다.

다른 풀이자의 코드

Hash 이용

def solution(participant, completion):
	hashDict = {}
    sumHash = 0
    
    # 1. HashMap 생성
    for part in participant:
    	hashDict[hash(part)] = part
        sumHash += hash(part)
    
    # 2. sumHash값에서 completion의 hash값을 빼서 미완주자 찾기
    for comp in completion:
    	sumHash -= hash(comp)
    
    return hashDict[sumHash]

participanthashDict

["leo", "kiki", "eden"]

{1696323092793078425: 'leo', -5687324499392274878: 'kiki', -3981211467484517104: 'eden'}

collections.Counter

import collections

def solution(participant, completion):
	answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

["leo", "kiki", "eden"]["eden", "kiki"]

Counter({'leo': 1, 'kiki': 1, 'eden': 1})

Counter({'eden': 1, 'kiki': 1})

 

Hash는 임의 값을 고정 길이로 변환하는 것이다.
Hashing 함수는 Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수이다.
파이썬에서는 Dictionary 자료구조가 Hash Table의 예이다. : Key를 가지고 Value를 꺼낼 수 있다.

❓ Hash를 사용해야 할 떄 ❓

1. 리스트를 쓸 수 없을 때
리스트는 숫자 인덱스를 이용하여 원소에 접근하는데 즉 list[1]은 가능하지만 list['a']는 불가능하다.
인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용하려고 할 때 딕셔너리를 사용하면 좋다.

2. 빠른 접근 / 탐색이 필요할 때
딕셔너리 함수의 시간복잡도는 대부분 O(1)이므로 아주 빠른 자료구조이다.

3. 집계가 필요할 때
원소의 개수를 세는 문제는 코딩 테스트에서 많이 출제되는 문제이다.
이때 해시와, collections 모듈의 Counter 클래스를 사용한다.

😐 collections.counter( )
보통 데이터의 개수를 셀 때 collections.Counter()을 사용한다.

dictionary를 이용한 카운팅

def countLetters(word):
    counter = {}
    for letter in word:
        if letter not in counter:
            counter[letter] = 0
        counter[letter] += 1
    return counter

countLetters('hello world'))
# {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

collections.Counter()을 이용한 카운팅

 

from collections import Counter

Counter('hello world') 
# Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})