프로그래머스-완주하지 못한 선수 파이썬 python

Level 1 완주하지 못한 선수 문제 풀이 입니다. 

링크 : https://programmers.co.kr/learn/courses/30/lessons/42576

 

문제 설명

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

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

 

제한사항

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

입출력 예

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

입출력 예 설명

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

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

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

 

사용한 솔루션 입니다

1   def solution(participant, completion): 2     participant=sorted(participant) 3     completion=sorted(completion) 4     for i in range(len(participant)-1): 5         if participant[i] != completion[i]: 6             return participant[i] 7     return participant[len(participant)-1]

해설

1   def solution(participant, completion):

participant, completion을 인자로 받고 있습니다. 

두 인자는 위 입출력 예와 같이 배열입니다.

이 문제에서는 효율성 테스트가 있기 때문에

제한 조건을 고려해서 풀어야 합니다.

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

N은 최대 10^5 입니다.

해당 풀이는 O(NlogN)입니다. 

 

 

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

위 제한 조건에서 알 수 있는 부분은 무조건 1명만 완주를 못한다는 것 입니다. 

 

 

• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

위 제한 조건을 보고 배열을 sort 해봐야 겠다는 생각을 했습니다.

문제 다 푼 후 다른 사람의 풀이를 보니 dictionary를 사용하는게 정석인듯 합니다!

우선 생각나는 대로 풀어보고 다른사람의 풀이도 분석해 보겠습니다.

2     participant=sorted(participant) 3     completion=sorted(completion)

>>

participant와 completion을 sorted 해줍니다. 

 

participant와 completion에 저장된 이름의 순서를 맞춰놓고

순서대로 체크했는데 다른 이름이 발견 된다면

완주 못한 사람이 발견 된 것이므로 return 을 해줘야합니다.

 

4     for i in range(len(participant)-1): 5         if participant[i] != completion[i]: 6             return participant[i]

>>

participant 를 순회하는 for 문을 만듭니다.

participant 길이 보다 1 작게 만든 이유는

completion이 participant보다 길이가 1 작기 때문입니다.

range(len(completion))으로 작성해도 무관할 듯 합니다. 

participant 를 모두 순회하면 오류가 발생합니다. 

가령, 완주자는 9명인데 참가자 10명을 순회한다고 하면 10번째 완주자는 존재하지 않으니 체크가 불가능 하니까요!

 

 

if 문을 통해 participant와 completion이 같은 이름인지 확인하는데

다른 이름이 나온다면 retrun 해줍니다. 완주를 못한 참가자 이름을 return 해야 하므로

participant[i]를 반환합니다.

 

 

7    return participant[len(participant)-1]

>>

for 문이 끝났는데 아무것도 return 한게 없다면

마지막 참가자가 완주하지 못한 선수 입니다. 

return participant[len(participant)-1] 로 마지막 참자자 이름을 반환합니다. 

 

##

처음에 위와 같이 풀었는데

다른 사람의 풀이를 보니 여러 풀이 방법이 있어 공부해 보고 가려 합니다. 

대표적으로 hash 를 이용한 풀이가 있어서 알고 가면 좋을 것 같습니다 !

hash table에 대한 공부는 하단 링크를 통해 공부했습니다.

참고 글 : https://www.fun-coding.org/Chapter09-hashtable.html 

해시 테이블은 key에 value를 저장하는 자료구조 입니다.

 key를 통해 바로 value에 접근 할 수 있기 때문에 속도가 매우 빠릅니다.

속도가 빠르다는 점을 이용한 알고리즘 문제를 자주 만날 수 있습니다.

꼭 공부해 둬야 할 자료구조입니다!

 

파이썬에서는 dictionary 타입을 통해 hash table을 만들 수 있습니다.

 

중복 주소에 대한 충돌을 해결할 자료구조가 별도로 필요하다는 단점이 있습니다.

 

1     def solution(participant, completion): 2        temp = 0 3        dict_hash = {} 4        for part in participant: 5            dict_hash[hash(part)]=part 6            temp += int(hash(part)) 7        for com in completion: 8            temp -=hash(com) 9        answer = dict_hash[temp] 10 11       return answer

1     def solution(participant, completion): 2        temp = 0 3        dict_hash = {}

>>

먼저, temp와 dict_hash를 선언하고 초기화 합니다.

temp는 hash를 담을 변수 입니다.

 

 

4        for part in participant: 5            dict_hash[hash(part)]=part 6            temp += int(hash(part))

>>

participant를 순회하여 이름(part)을 hash로 바꿔 줍니다.

이것을 key로 dictionary 에 이름(part)을 value로 저장합니다. 

dict_hash에는 

( hash(part) : part) 가 저장됩니다.

예를 들자면,

( '123' : '철수' ) 로 저장 됩니다.

dict_hash에 저장된 key - value 쌍을 통해 완주 못한 참가자를 찾아낼 수 있습니다. 

 

temp에는 hash들을 정수로 변환하여 누적 합산 합니다. 

 

 

7        for com in completion: 8            temp -=hash(com) 9        answer = dict_hash[temp] 10 11       return answer

>>

completion을 순회 합니다.

participant를 순회하며 누적합을 계산했던 temp에서

다시 hash(com)을 누적 감산합니다.

이렇게 하는 이유는 완주 하지 못 한 사람이 단 한 명이기 때문에

마지막에 남은 hash값이 단 한명을 가리키기 때문입니다. 

 

for문이 다 돌면 temp(hash)가 가리키는 한 명을 알 수 있습니다. 

answer에 dict_hash[temp] 대입하고 반환합니다. 

 

 

::

hash 사용에 숙련도가 높지 않음을 많이 느껴요ㅠ

풀기 어려운 문제는 아니었지만

사람에 따라 푸는 방법이 많이 갈렸던 문제였던 것 같습니다. 

hash 가 아닌 collections 라는 모듈로 푼 풀이, zip으로 푼 풀이 등등 

다양한 풀이 방법이 있다는것에 놀라울 뿐😱... 

 

 

문제 푸시느라 고생하셨습니다!