15. 완주하지 못한 선수
코딩테스트 연습 > 해시 > 완주하지 못한 선수
https://programmers.co.kr/learn/courses/30/lessons/42576
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
ㆍ 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
ㆍ completion의 길이는 participant의 길이보다 1 작습니다.
ㆍ 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
ㆍ 참가자 중에는 동명이인이 있을 수 있습니다.
participant = "leo", "kiki", "eden"
completion = "eden", "kiki"
return = "leo
participant 문자열 리스트에 있는 원소를 뽑아 completion과 비교
해당 원소가 completion에 있을 경우,
1-1. completion에서 해당 원소를 pop한다.
※ 해당 부분에서 시간복잡도가 증가하여 효율성테스트 실패..
1-2. 없을 경우 해당 원소를 return 한다.
# 일반 방법 - 시간 초과 발생
def solution(participant,completion):
sorted(participant)
sorted(completion)
for p in participant:
if p in completion:
completion.pop(completion.index(p))
else:
return p
# Code test
participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
solution(participant,completion)
동명이인의 경우를 고려하여 Counter을 이용하여 각 원소의 갯수를 딕셔너리 형태로 출력
ex)
import collections
participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
collections.Counter(participant)=({'leo':1, 'kiki':1, 'eden'=1})
collections.Counter(completion) =({'eden':1,'kiki':1})
해당 방법을 통해 Participant 리스트에서 Completion 리스트를 빼면 남은 원소의 key값이 해당 문제에서 요구하는 답이 된다.
# Collections 라이브러리의 Counter를 써서 문제 해결
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]
# Code test
participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]