[Programmers][해시(Hash)] 완주하지 못한 선수 python (211028)

문제

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

이해도

★★☆☆☆

소감

• 이름 갯수(1~20개 알파벳 소문자), 동명이인 여부에 낚여서 헤매었다. 이 문제에서는 필요가 없었다.
• 해시를 어떻게 적용해야할지 고민이 되어서 쉬운 문제인데도 접근이 어려웠다.
• 인덱스를 비교해도 되고, 해시맵을 사용해도 된다. 

방법 1. 반복문 돌며 인덱스 비교하기

두 리스트의 인덱스를 비교해서 해당 값이 다르면 완주를 못한 사람임을 알 수 있다.

먼저 인덱스를 비교하기 위해 각 리스트를 정렬해야 한다.

원본 리스트는 필요 없으므로 sorted 메서드를 사용한다.

이후 완주자 수(참가자 수 -1) 만큼을 돌면서 인덱스를 비교한다.

다르면 미완주니까 참가자수에서 해당 인덱스를 반환하고, 

다 돌았으면 마지막 참가자만 남기 때문에 리스트 마지막 값을 반환한다.

 

# 1. 두 리스트를 sorting 한다.

# 2. completion list의 length만큼 돌면서, participant에만 존재하는 한명을 찾는다.

# 3. 다 돌아도 답이 없으면 마지막 참가자가 미완주자가 된다.

 

def solution(participant, completion):
    # 인덱스 비교 위해 정렬
    participant.sort()
    completion.sort()

    # 완주자 수(참가자 수-1) 만큼 돌면서 인덱스 비교, 다르면 미완주
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    # 다 돌았으면 마지막 참가자가 미완주
    return participant[-1]

 

방법 2. 해시맵 사용하기

딕셔너리 형태로 해시맵을 만들면 key에 해시값이, value에 선수들 이름이 들어간다.

이때 참가자들로 만든 해시맵 key값을 모두 합친 값을 구한다.

그 값에서 완주자를 다 돌면서 key값을 모두 빼주면,

남은 값이 곳 완주하지 못한 선수의 hash 값이 된다.

 

# 1. participant list의 hash를 구하고, hash 값을 더한다.

# 2. completion list의 해시를 빼준다.

# 3. 남은 값이 완주하지 못한 선수의 hash 값이 된다.

 

# 해시맵(딕셔너리)

def solution(participant, completion):
    # 해쉬 넣을 딕셔너리 만든다.
    hashDict = {}
    sumHash = 0

    # participant 의 해시를 구하고, 해시맵(딕셔너리)에 더한다.
    for part in participant:
        hashDict[hash(part)] = part
        # 해시의 합을 더한다.
        sumHash += hash(part)

    # completion 을 돌면서 해시값을 뺀다.
    for comp in completion:
        sumHash -= hash(comp)

    # 남은 값이 곧 완주하지 못한 선수의 hash 값이므로 딕셔너리에서 찾아 반환한다.
    answer = hashDict[sumHash]
    return answer

 

방법 3. Counter 클래스를 활용하기

"a dict subclass for counting hashable objects." collections 모듈 내의 counter 클래스. 

리스트를 딕셔너리로 변환 후 반환해준다. 

 

a = Counter()                           # a new, empty counter
b = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
d = Counter(cats=4, dogs=8)             # a new counter from keyword args

>>> Counter()
>>> Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})
>>> Counter({'red': 4, 'blue': 2})
>>> Counter({'dogs': 8, 'cats': 4})

 

# 1. participant의 counter를 구한다.

# 2. completion의 counter를 구한다.

# 3. 둘의 차를 구하고, key를 읽어온다.

 

from collections import Counter

def solution(participant, completion):
    part_counter = Counter(participant)
    comp_counter = Counter(completion)

    remain = (part_counter - comp_counter)  # >>> Counter({'leo': 1})
    # print(remain.keys()) >>> dict_keys(['leo'])
    # print(list(remain.keys())) >>> ['leo']

    return list(remain.keys())[0]

 

보다 간단하게

from collections import Counter

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

 

 

참고자료 : https://coding-grandpa.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98-%ED%95%B4%EC%8B%9C-Lv-1