Level 1 | Python | 완주하지 못한 선수(해시)

1. 문제설명

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

participant : 마라톤에 참여한 선수들 이름이 담긴 배열 

completion : 완주한 선수들 이름이 담긴 배열

위와 같이 변수가 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

<중요제약조건>

참가자 중에는 동명이인이 있을 수 있습니다.

2. 주의해야 했던 점

- 쉬운문제라고 단순하게 생각해서 정렬도 안된상태로 둘을 비교하거나,
- 정렬을 했더라도 같은걸 찾았을 때 중간에서 pop 해서 없애버리는 방식은 리스트의 중간에서 이뤄나는 연산이므로 O(n)의 복잡도로 인해서 효율성 평가에서 막혀버렸었다.

- 이에 삽입자체가 O(1)의 복잡도를 가지는 dict 데이터형(해시테이블 알고리즘을 기반으로 만들어짐)을 사용하였다.

- 리스트 원소의 개수를 체크할 때 count 메소드를 사용하면 효율면에서 떨어져 합격할 수 없었다.

3. 내 풀이

def solution(participant, completion):
    answer = ''

    # 이름의 개수를 센 딕셔너리를 참가자, 완주자에 대해서 각각 만듬
    p_dic = make_dictionary(participant)
    c_dic = make_dictionary(completion)

    # 중복된 이름이 없다면 1개만 나올 것임
    lst = list(set(p_dic.keys()) - set(c_dic.keys()))

    # 중복된 이름이 없는 경우
    if len(lst) == 1:
        answer = lst[0]
    # 중복된 이름이 있는 경우
    elif len(lst) == 0:
        for p in participant:
            if p_dic[p] != c_dic[p]:
                answer = p
                break

    return answer


# 참가자 혹은 완주자 리스트로 이름을 카운트한 딕셔너리 생성
def make_dictionary(lst):
    dic = {}

    for item in lst:
        keys = dic.keys()
        # 딕셔너리에 없다면 생성 후 1로 초기화
        if item not in keys:
            dic[item] = 1
        # 딕셔너리에 있다면 카운트 1증가
        else:
            dic[item] += 1

    return dic

4. 다른 사람 풀이

import collections


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