프로그래머스 - 완주하지 못한 선수 (해시)

이번 포스팅에서는 프로그래머스의 완주하지 못한 선수 (해시) 코딩테스트 연습 문제를 풀어봅니다.

문제 설명

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

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

제한사항

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

입출력 예

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

입출력 예 설명

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

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

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

문제 풀이

마지막 제한사항인 참가자 중에서 동명이인이 있을 수 있습니다가 아니라면 다음과 같이 set의 차집합을 이용할때 쉽게 결과를 얻을 수 있습니다.

solution = lambda participant, completion: (list(set(participant) - set(completion))[0])
print(solution(["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]))

vinko

하지만 이번 문제는 중복을 허용하는 문제 입니다. ㅠㅠ 그래서 딕셔너리를 이용하여 참여자 명단에 대한 카운트를 하고 완주자 명단에서 카운트를 하나씩 빼서 1이 남은 사람의 명단을 출력하 도록 하였습니다.

def solution(participant, completion):
    dic = {}
    for p in participant:
        try: dic[p] += 1
        except: dic[p] = 1

    for c in completion:
        dic[c] -= 1
    return sorted(dic.items(), key = lambda x : -x[1])[0][0]

print(solution(["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]))
print(solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]))

vinko
mislav

결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.

그런데 혹시 중복 요소의 갯수를 카운트 해주는 기능이 없을까 찾아 보았습니다만…. 역시나 파이썬에는 존재 하였습니다. 역시 파이썬… ㅎㅎ
collections의 .Counter()함수를 이용하면 리스트의 요소를 key로 저장하고 중복요소는 카운트하여 value에 넣어 줍니다. 코드로 확인해 보겠습니다.

import collections

def solution(participant, completion):
    print(collections.Counter(participant))
    print(collections.Counter(completion))

solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"])

Counter({‘mislav’: 2, ‘stanko’: 1, ‘ana’: 1})
Counter({‘stanko’: 1, ‘ana’: 1, ‘mislav’: 1})

.most_common(n)을 이용하면 n 개의 가장 흔한 요소와 그 개수를 가장 흔한 것부터 가장 적은 것 순으로 나열한 리스트를 반환해 주네요!

import collections

def solution(participant, completion):
    print(collections.Counter(participant).most_common(3))
    print(collections.Counter(completion).most_common(1))

solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"])

[(‘mislav’, 2), (‘stanko’, 1), (‘ana’, 1)]
[(‘stanko’, 1)]

Counter 객체를 결합하여 멀티 셋 수학 연산(교집합, 합집합, 차집합)이 제공됩니다. 이번 문제에서는 차집합을 이용할 수 있겠네요 한번 해보도록 하겠습니다.

import collections

def solution(participant, completion):
    print(collections.Counter(participant) - collections.Counter(completion))

solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"])

Counter({‘mislav’: 1})

위의 개념들을 사용하여 문제에 맞게 완주하지 못한 선수를 찾아 보겠습니다. 그리고 한줄 코드록 작성해 보았습니다.

import collections

solution = lambda participant, completion: ((collections.Counter(participant) - collections.Counter(completion)).most_common(1)[0][0])

print(solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]))

mislav

collections에는 전에 이용한 deque에 이어서 counter 기능까지 유용한 기능이 많은거 같습니다. 이 외에 여러가지 기능을 공부해 봐야 할 거 같습니다.