이분의 풀이를 참고하여 문제 풀이를 시작했다.
이 분은 두개의 배열을 비교하는 문제라고 생각하고 접근했다고 한다.
나는 문제 읽기도 어려웠는데 어떻게 이런 생각을?😮
하고 다시 찬찬히 문제를 읽었다.
참가자 배열과 완주한 선수들의 이름이 담긴 배열이 주어질 때,
완주하지 못한 선수들의 이름을 retrun 하도록 하라고 했으니
아 두 배열을 비교해 완주 못한 사람만 retrun 하면 되겠구나 하는 생각을
나도 해볼 수 있었다. (ง •̀_•́)ง
but 시간복잡도에서의 효율성이 떨어지는 모양이었다.
게다가 알고보니 자바스크립트로 푸셔서
파이썬으로 푼 분의 풀이를 찾고자 좀 더 검색해봤다.
https://coding-grandpa.tistory.com/85
이분은 문제 접근 방식 부터 설명해 주셨다.
문제를 간단하게 만들어 보라고 한다.
다시 문제를 봤다. 이분의 설명처럼 participant의 배열에는 n명의 참가자가 있었고,
completion 배열에는 n-1명의 완주자들이 있었다.
결론은 위의 분과 똑같았다. 좌우를 비교해 없는 것 하나를 찾으면 되는 것
여러 해결책을 주셨지만 이 코테 킷은 해시문제를 다루는 킷이기에
해시로 풀이해보려고 한다.
hashmap 만들기
hashmap은 key-value의 페어를 관리하는 클래스 이다.
이 문제에서 key는 hash한 값(고정던 길이)이 되고
value는 각 선수의 이름으로 한다고 한다.
이분 설명 너무 잘하신다 이해가 쏙쏙 됨...
key에는 각 선수 값의 고유 번호를 value에는 각 선수의 이름을 넣는다.
각 이름의 hash값을 구하면 모든 해시 값의 합인 sumHash를 얻을 수 있다.
이 sumHash에서 완주자들의 key 값을 빼면
완주하지 못한 사람만 남을 수 있게 된다.
그럼 실제로 풀어보자!
def solution(participant, completion):
hashDict = {}
sumHash = 0
for part in participant:
hashDict[hash(part)] = part #파이썬 hash(some)은 some에 hash값을 부여해 준다.
sumHash += hash(part)
for comp in completion:
sumHash -= hash(comp)
return hashDict[sumHash]
print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))감사합니다 🐇
