🏀 문제

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

문제는 따로 설명하지 않고, 링크를 첨부.

💡 접근 방식

첫 번째 생각한 방식은
list 형태로 input이 넘어오기 때문에 sort한 후에 완주자와 참가자를 비교하려고 했음.
sort를 한다면 평균 시간복잡도가 최소 O(nlogn) 소요된다고 생각해서, 제한 조건대로 10만명까지 참가자가 늘어나면, 비효율적이라고 생각함.

참고사항
다른 분이 정렬 알고리즘 시간복잡도 정리해논 링크 첨부했습니다.
https://program-developer.tistory.com/106

최종 접근 방식은
"참가자를 [참가자 이름, cnt] 받는 dict를 만들고, 완주자를 for문으로 순회하면서 완주한 경우는 -1을 해주자. 그러면 value가 0이 아닌 경우 완주를 못한 사람이다." 라는 생각으로 접근했습니다.
이 때 고민한 부분은

• 동명이인 : cnt를 value 값으로 받게 설정
• dict를 만드는 것의 복잡도 : worst case가 O(n)// for문 O(n) 이고 모두가 동명이인이 아닌 경우 성능적인 부분도 장점
  즉, sort 보다 성능적인 장점이 있다고 생각해서 선택했습니다.

🔧 코드

from _collections import defaultdict
def solution(participant, completion):
    answer=''
    #[leo, kiki, eden], [eden, kiki]
    try:
        if len(participant) - len(completion) != 1 :
            raise Exception('길이 차이 제한')
        p_dict = defaultdict(int)
        for p_key in participant:
            if (p_key.isalpha() != True) and len(p_key) > 20:
                raise Exception('참가자 사람 이름 제한')
            p_dict[p_key] += 1
        for c_key in completion:
            if (c_key.isalpha() != True) and len(c_key) > 20:
                raise Exception('완주자 사람 이름 제한')
            p_dict[c_key] -= 1
        for key,val in p_dict.items():
                if val != 0:
                    answer = key
                    break
    except Exception as e:
        print(e)
    
    return answer

💎 다른 사람의 풀이 참고

 def solution(participant, completion):
     dict = {}
     key = 0
     for p in participant:
         dict[hash(p)] = p
         key += int(hash(p))
     for c in completion:
         dict[hash(c)] = c
         key -= int(hash(c))
     answer = dict[key]
     return answer

dict를 만든 후 저의 코드는 다시 순회해서 answer를 찾았지만, 이분은 key를 미리 hash를 통해서 바로 접근할 수 있도록 세팅해두었음.
이런 식으로 dict를 사용할 때 key 값도 고려해줄 수 있으면 성능적인 요소에 장점이 있다는 걸 배움.