[Python 프로그래머스] 완주하지 못한 선수 - 초보를 위한 자세한 설명 | 해시 알고리즘

문제 주소:
https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

---

해쉬 문제입니다.

해쉬 구조란?

• 키(Key)와 값(Value) 쌍으로 이루어진 데이터 구조를 의미합니다. Key를 이용하여 데이터를 찾으므로, 속도를 빠르게 만드는 구조입니다.
• 파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조입니다.
• 기본적으로는, 배열로 미리 Hash Table 크기만큼 생성해서 사용합니다. 공간은 많이 사용하지만, 시간은 빠르다는 장점이 있습니다.
• 검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용됩니다.
• 장점
  • 데이터 저장/검색 속도가 빠릅니다.
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽습니다.
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요합니다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요합니다. (충돌 해결 알고리즘)
• 시간 복잡도
  • 일반적인 경우(충돌이 없는 경우): O(1)
  • 최악의 경우(모든 경우에 충돌이 발생하는 경우): O(n)

출처: https://davinci-ai.tistory.com/19 [DAVINCI - AI]

---

문제 설명

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

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

---

제한사항

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

---

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

 

---

입출력 예 설명

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

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

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

---

나의 풀이

def solution(participant, completion):
    answer = ''
    
    # 동명이인이 없는 경우를 먼저 해결 
    part = set(participant)
    completion = set(completion)
    temp = part - completion
    if len(temp) >= 1:
        return list(temp)[0]
   
    # 동명이인이 있어서 위의 if문에 걸리지 않았을 경우 아래의 루프로 해결
    for i in range(len(participant)):
        if participant[i] not in completion:
            return participant[i]
        else:
            completion.remove(participant[i])
    return answer

사실 이건 정답 처리가 안됩니다. 이 문제는 정확성 테스트와 효율성 테스트가 따로 있었는데 제 코드는 효율성 테스트 맨 마지막을 통과하지 못했습니다..(아래 사진) 

해쉬 구조에 대해서 찾아보고 대충 이해는 했는데 어떻게 이 문제에서 응용해야할지 모르겠더군요. 그러니 제 코드는 그만 보고 다른 사람의 훌륭한 코드를 보실까요?

---

다른 사람의 훌륭한 풀이

def solution(participant, completion):
    answer = {}
    
    # 예를 들어 participant = ['a', 'b', 'b'] 일 경우
    # answer = {'a': 1, 'b': 2} 와 같은 형태가 된다.
    for i in participant:
        answer[i] = answer.get(i, 0) + 1
       	
    # completion 에 포함되는 이름의 key 의 value 를 -1 한다.   
    for j in completion:
        answer[j] -= 1
        
    # participant 에는 있지만 completion 에는 없는 이름만 value 가 1로 남게되니 그것을 리턴한다.    
    for k in answer:
        if answer[k] : return k

코드출처: https://mungto.tistory.com/193

프로그래머스 "다른 사람의 풀이" 페이지에는 더 간결한 코드도 있었는데 이 분이 작성하신 게 문제 출제자의 해시를 이용하라는 의도와 더 적합하다고 생각하여 이걸 가져왔습니다. 그리고 시험해봤는데 속도도 더 빨라요.

기타 문법 설명

• get() 함수 사용법
   - dictionary 자료형과 함께 사용합니다.
  

   dict.get(key, value)

  key - dictionary 에서 찾을 키
  value - key를 찾기 못했을 경우 리턴할 값. 설정하지 않아도 됩니다. 디폴트 값은 none
  
  예제 코드
  

     person = {'name': 'Phill', 'age': 22}
  
  print('Name: ', person.get('name'))
  print('Age: ', person.get('age'))
  
  # value is not provided
  print('Salary: ', person.get('salary'))
  
  # value is provided
  print('Salary: ', person.get('salary', 0.0))

---

짧은 후기

해쉬 구조와 get 함수를 알게되었어요.