[LV1] 완주하지 못한 선수 - Python(해시)

[LV1] 완주하지 못한 선수

---

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

---

제한 사항

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

---

입출력 예#1

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

---

입출력 예#2

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

---

입출력 예#3

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

---

입출력 예시 

---

풀이 및 코드 리뷰

내가 제출한 답 (오답)

def solution(participant, completion):
    answer = 0
    for part in participant:
        if part not in completion:
            answer = part
            break
        elif part in completion :
            completion.remove(part)    
            
    return answer

 

• 처음 제출한 문제의 답이다. 참가자에서 각 문자를 추출하여 완주자와 비교하여 동명이인을 제외한 나머지 값들을    추출 하였다.
• 동명이인의 경우 참가자들을 완주자와 1명씩 비교하여 완주자에 참가자가 있는경우 참가자를 제거하여 남은 사람을 return값으로 하였다.
• 그러나 100000개 이상의 입력값에 따른 시간복잡도의 문제로 리스트 형태로 문제를 풀게될시 정확도가 만점일지 몰라도 효율성이 0점이 나왔다.

---

다른 사람의 풀이1

import collections 

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

• collections.Counter()을 사용하여 차집합을 구할수 있다
• List내 각 값들과, 그 값들이 몇개씩 있는지 확인할수 있음 Dictionary 방식으로 출력된다.

다른 사람의 풀이2

# 딕션어리 자료형으로 표현
# k, v = 사람이름, 그 이름에 대한 사람 수
# 참가를 하면 value +1 / 완주를 하면 value -1
# ---> 1명만 있었다면, key를 삭제
# 마지막에 value == 1인 key가 못들어온 사람

def solution(participant, completion):
    answer =""
    # 0) 자료를 정리할 나의 변수 & 자료형
    people_dict = {}
    # 1) 참가자들을 가지고 리스트 업 : name_count (+)
    for p in participant:
        # 이미 등록된 이름이냐 -> +1 (갱신)
        if p in people_dict: # True : 이미 등록된 이름
            people_dict[p] += 1
        # 새로운 이름이냐 => 이름도 등록, 값 = 1 (신규등록)
        else :
            people_dict[p] = 1
        
    # 2) 완주자에 대한 정리 : name_count (-)-> 참가자들을 지울 것..
    # 완주자 1명씩 불러다가 이름이 뭔지 물어보는 과정
    for p in completion:
        # 1명만 참가를 하고, 완주를 했는지
        if people_dict[p] == 1:
            del people_dict[p]
        # 2명 이상 참가를 했고, 완주를 했는지
        else :
            people_dict[p] -= 1
    
    # 최종결과) value == 1인 key가 정답
    answer = list(people_dict.keys())[0]
    return str(answer)

 

---

참고 자료

1. 해시 (Hash)  : 임의의 길이의 입력 데이터나 메시지를 고정된 길이의 값이나 키로 변환하는 것, 해시   알고리즘을  해시 함수라고 부르며,  해시 함수로 변환된 값이나 키를 해시값 또는 해시키라고 부른다.

2. collections.Counter()  :  파이썬에 내장되어 있는 collections 모듈의 Counter 클래스를 이용하면 리스트, 딕셔너리, 문자열 등의 데이터의 개수를 딕셔니리의 형식으로 출력이 가능하다

3. 소스코드 예제

from collections import Counter
리스트 = ["a",2,3,4,"b",3,4,"b",1]
딕션 = {"a":1, "b":2, 3:2}
문자열 = "aa231bb231211"
print(Counter(리스트))
print(Counter(딕션))
print(Counter(문자열))

결과