주제 - “알고리즘 (해시) - 1”

부제 - 프로그래머스 코딩테스트 연습 - 파이썬

출처 - 프로그래머스 - 코딩테스트 연습 - 해시 - 완주하지 못한 선수

​ - 문제의 풀이는 다른 사람의 풀이 중 공부하고 싶은 것을 스크랩한 것입니다.

문제 1. 완주하지 못한 선수

[문제 설명]

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

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

[제한사항]

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

[입출력 예]

풀이

from collections import Counter

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

풀이의 포인트

참가자 리스트인 participant에서 완주자 리스트 completion의 멤버들을 다 제외했을 때 남는 1개의 값을 추출하는 문제입니다.

'’참가자 중 동명이인이 있을 수 있다’’ 는 제한 사항 때문에, 단순히 list를 set으로 변환하여 - 연산을 하는 것은 불가능합니다. set은 중복을 허용하지 않기 때문입니다. 그렇기에 동명이인을 추출하는 작업이 선행되어야 합니다.

1) collections 모듈의 Counter : hashable objects를 카운팅하기 위한 dict의 서브클래스

hashable : 매칭되는 해시값이 있고, 그 값이 변하지 않는 경우

ex)

>>> a = 'cocojelly'
>>> a.__hash__()
-6863412972335055948

Counter 사용 예시

>>> c = Counter('cocojelly')
>>> c
Counter({'c': 2, 'o': 2, 'l': 2, 'j': 1, 'e': 1, 'y': 1})

>>> c = Counter(['eggs', 'ham'])
>>> c
Counter({'eggs': 1, 'ham': 1})

>>> c = Counter({'red': 4, 'blue': 2})
>>> c
Counter({'red': 4, 'blue': 2})

>>> c = Counter(cats=4, dogs=8)
>>> c
Counter({'dogs': 8, 'cats': 4})

동명이인을 추출하기 위해, Counter를 사용하여 각 이름에 해당되는 인원수를 카운팅합니다.

>>> participant = ["mislav", "stanko", "mislav", "ana"]

>>> p = Counter(participant)
>>> p
Counter({'mislav': 2, 'stanko': 1, 'ana': 1})

>>> completion = ["stanko", "ana", "mislav"]

>>> c = Counter(completion)
>>> c
Counter({'stanko': 1, 'ana': 1, 'mislav': 1})

2) Counter끼리의 - 연산

list나 dict 끼리는 - 연산을 수행할 수 없지만, Counter 끼리는 - 연산 수행이 가능합니다.

이를 수행하면 같은 key에 해당하는 value 를 뺄셈하여, 결과를 Counter로 리턴합니다. 이 때, value가 0보다 큰 값만이 남아있게 됩니다. (value가 0 이하인 값을 얻기 위해서는 subtract를 사용해야 합니다.)

>>> a = Counter({'c': 2, 'o': 2, 'l': 2, 'j': 1, 'e': 1, 'y': 1})
>>> b = Counter({'c': 2, 'o': 1, 'l': 1, 'j': 1, 'e': 1, 'y': 1})

>>> c = a - b
>>> c
Counter({'o': 1, 'l': 1})

>>> a.subtract(b)
Counter({'o': 1, 'l': 1, 'c': 0, 'j': 0, 'e': 0, 'y': 0})

이를 문제에 적용하면, 이름별 인원수에 대한 뺄셈을 수행할 수 있습니다.

>>> p
Counter({'mislav': 2, 'stanko': 1, 'ana': 1})

>>> c
Counter({'stanko': 1, 'ana': 1, 'mislav': 1})

>>> answer = p - c
>>> answer
Counter({'mislav': 1})

3) Counter의 키값을 문자열의 형태로 리턴

Counter에서 .keys()를 통해 key 값만을 추출해내면 그 타입은 dict_keys가 됩니다. 이를 list로 변환하고 그 중 첫번째 값을 추출하면 문자열 형태의 값이 리턴됩니다.

( 완주하지 못한 선수는 1명이라는 전제가 있었으므로 list의 길이는 반드시 1입니다. )

>>> answer
Counter({'mislav': 1})

>>> answer.keys()
dict_keys(['mislav'])

>>> list(answer.keys())
['mislav']

>>> list(answer.keys())[0]
'mislav'

이어서 - [프로그래머스 - 코딩테스트 연습] 해시 (2)