[Lv2.] 해시 - 완주하지 못한 선수

👉 사용 언어 : PYTHON3

완주하지 못한 선수

✅ Solution

def solution(participant, completion):
    res = {name:participant.count(name) for name in participant}
    for comp_name in completion:
        res[comp_name] -= 1
    return [name for name in res.keys() if res[name] > 0][0]

: 효율성 테스트에서 시간초과 발생

def solution(participant, completion):
    res = {name:0 for name in participant}
    for name in participant:
        res[name] += 1
    for comp_name in completion:
        res[comp_name] -= 1
    return [name for name in res if res[name] > 0][0]

: 메모리: 33.9 MB, 시간: 81.94 ms

 

👉 문제 설명 및 제한 사항

• 매개변수 : 마라톤에 참여한 선수들의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion
  • 1 <= 마라톤 경기에 참여한 선수의 수 <= 100,000
  • completion 길이 = participant 길이 -1
  • 참가자 이름 : 1개 이상 20개 이하의 알파벳 소문자
  • 참가자 중에는 동명이인이 있을 수 있음
• 리턴값 : 완주하지 못한 선수의 이름

👉 아이디어

• 동명이인이 있을 수 있다는 조건때문에 딕셔너리나 집합을 쓸 경우 유의해서 사용해야 함 (중복X)
• 첫번째 풀이
  • 딕셔너리를 생성할 때, 참가자 이름을 key로 이름이 나온 횟수를 value로 지정한다.
    • 동명이인이 있으면 해당 이름의 key에 그 수만큼 value를 맵핑된다.
  • 완주한 선수 명단에서 하나씩 이름을 추출하여 딕셔너리에서 그 이름에 맵핑된 값을 -1 한다.
  • 딕셔너리에서 값이 0보다 큰 key(이름)을 리턴한다.
  • for문 안에서 count()를 사용해 시간초과가 발생한 듯하다. 참여 선수가 최대 100,000명이므로❗️
    • O(N^N)❓❗️: for문에서 len(participant) * count에서 len(participant)
• 최종 풀이
  • 첫번째 풀이와 아이디어는 비슷하나, 딕셔너리를 생성하고 값에 -,+ 연산을 적용하는 과정을 다르게 구현했다.
  • 딕셔너리를 생성할 때, key는 참가자 이름을 value는 모두 0으로 지정한다.
  • participant에서 하나씩 이름을 추출하여 참여 선수 이름에 해당하는 값을 +1 한다. (동명이인도 모두 체크)
  • completion에서 하나씩 이름을 추출하여 완주한 선수 이름에 해당하는 값을 -1 한다.
  • 딕셔너리에서 값이 0보다 큰 key(이름)을 리턴한다.
  • 반복문을 따로 분리하여 O(N*2+M) : for문에서 len(participant) * 2 + for문에서 len(completion)

✅ 다른 사람 풀이 참고

import collections


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

 

👉 깨달은 것 / 알게된 것

• Counter 객체는 빼기가 가능하다❗️
• 아이디어가 비슷해도 구현 과정에서 시간복잡도를 고려하여 구현하면 시간 초과 발생을 방지할 수 있다❗️
• Collections 모듈의 Counter 객체 설명 참고 > https://mungchstudy.tistory.com/82 https://mungchstudy.tistory.com/83