코딩테스트 고득점 kit, 해시 - 완주하지 못한 선수

문제설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

입출력 예

입출력 예 설명

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

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

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

---

이 문제의 key포인트

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

이 제한조건이 없다면 for문을 돌려서 if not in ~으로 이름의 포함여부만 확인하면 되지만 해당 조건이 있으므로 각 이름의 개수를 세서 중복을 고려해줘야한다.

---

자료구조 및 알고리즘: 해시

---

풀이

각 이름의 개수를 쉽게 넣고 조회할 수 있도록 해시를 사용하기로 하였다.

처음에는 각 이름의 개수를 해시에 넣고 completion 리스트를 돌면서 이름에 따른 count값을 해시에서 1씩 감소시켜 for문을 모두 돌았을 때 아직 count값이 0이 아닌 key값을 출력하도록 했다. 정확성 검사는 모두 통과했지만 효율성 검사에서 모든 TC가 시간초과가 났다.

 

첫번째 풀이 (정확성: O, 효율성: 시간초과)

def solution(participant, completion):
    # 이름의 개수를 해시에 넣고 completion 리스트 돌면서 해시값을 1씩 감소시킴
	# for문을 다 돌아도 개수가 0이 아닌 애 key값을 출력
    answer = ""
	# participant 해시에 집어넣기
    part_dict = {}
    for i in range(len(participant)):
        temp = list(part_dict.keys())
        name = participant[i]
        if name in temp:
            part_dict[name] += 1
        else: part_dict[name] = 1
        
    temp2 = list(part_dict.keys())
    # 해시에서 completion에 나온 이름 수만큼 빼기
    for j in range(len(completion)):
        name = completion[j]
        if name in temp2:
            part_dict[name] -= 1
        else: 
            answer = name
            return answer
	
    # 다 뺐는데 남아있는 해시값 출력    
    for k in range(len(part_dict)):
        if part_dict[temp2[k]] != 0:
            answer = temp2[k]
            return answer

 

시간을 줄이기 위한 방법으로 Counter를 사용해보았다. Counter는 리스트에서 요소의 개수를 카운팅해주는 라이브러리로 실행결과가 dictionary로 나온다. 이 문제를 통해 dictionary간의 합 또는 차 계산을 할 수 있다는 것을 알게되었다.

1. participant와 completion 각각 Counter을 이용해 각 이름의 개수를 센다.
2. part_dict - comp_dict 를 하면 part_dict 에만 있거나 완주하지 못한 남은 한 명이 딕셔너리로 나온다.
3. keys() 함수를 이용해 temp의 key값을 꺼내고 이를 리스트로 묶어서 answer에 저장한다.

Tip: dict를 list로 바꾸면 dict.keys()와 동일한 리스트가 나온다.

part_dict = {"leo":1,"kiki":1,"eden":1}
temp = {"leo":1}
list(part_dict) # ["leo","kiki","eden"]
list(temp) # ["leo"]

 

두번째 풀이 (정확성: O, 효율성: O)

from collections import Counter

def solution(participant, completion):
    # Counter의 결과가 해시다!
    part_dict = Counter(participant) # {"leo":1,"kiki":1,"eden":1}
    comp_dict = Counter(completion) # {"eden":1,"kiki":1}
    temp = part_dict - comp_dict # {"leo":1}
    answer = list(temp)[0]
    
    return answer