2023 04 07 완주하지 못한 선수

문제 설명

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

 

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

completion의 길이는 participant의 길이보다 1 작습니다.

참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

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

 

처음에는 list filter를 통해 접근을 하면되지않을까! 하고 접근을 해봤지만 가장중요한 제한사항인 동명이인의 벽을 넘을 방법을 생각하지못했습니다

list(filter(lambda x: x not in completion , participant))

이 코드를 사용하면 동명이인의 경우가 판단이 되질않아서 다른 방법을 생각하게 되었습니다

 

그 다음으로 생각한 방법은 set을 이용한 방법... 이거또한 set을 사용시에 중복이 제거되기 때문에 불가능...

 

그다음에 remove를 사용해서 하는방법은 시간복잡도에서 out...

 

시간복잡도를 고려해야한다는거를 이때알아서 딕셔너리를 활용해볼까 하는 생각으로 

일단 참여자들의 이름을 전부 딕셔너리에 name : <count> 방식으로 저장이되게

for partci in participant:
        if partci in count:
            count[partci] += 1
        else:
            count[partci] = 1

해당코드를 다시 사용해서 작성했습니다

 

그후 완주자들은 -1 을 하게되어서 동명이인의 경우에도 1이되고  아닌경우에도 미완주자는 1이남는 코드를만들었습니다

 

for complet in completion:
	count[complet] -= 1

그후 for 문을 통해서 data값이 0을초과하는 데이터를 리턴하는 방식으로 문제를 해결했습니다

for key, value in count.items():
    if value > 0:
        return key