문제

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

나의 코드 (답안참조)

"""
1. 아이디어
해시 문제이므로 해시 자료구조를 이용해서 푸는게 낫다.

참가자를 기준으로 for문을 돌면서
hashdict라는 딕셔너리 안에 각각의 해시값을 키로, 이름을 값으로 넣은 다음에
sumhash라는 정수형 변수에 해시값을 전부 입력한다.

그다음 완주자를 기준으로 for문을 돌면서
sumhash안에 정수형을 전부 빼준다.

결국, 마지막에 sumhash안에는 완주하지 못한 참가자의 해시값이 남을 것 이므로
키 값을 이용해서 참가자의 이름인 값을 뽑아낸다.

2. 시간복잡도
O(N) - 반복문 O(N), 해시 O(1)
"""

def solution(participant, completion):
    
    hashdict = {}
    sumhash = 0
    
    for person in participant:
        
        hashdict[hash(person)] = person
        sumhash += hash(person)
        
    for person in completion:
        sumhash -= hash(person)
    
    return hashdict[sumhash]

다른 사람의 풀이

"""
1. 아이디어
이름순으로 정렬한 후 참가자와 완주자의 이름을 각각 비교하면서 이름이 다를 경우는
완주하지 못한 참가자 이므로 그 즉시 반환하고 만약 반복문 안에서 반환이 안된다면
마지막 참가자가 완주하지 못한 경우 이므로 참가자의 마지막 이름을 반환한다.

2. 시간복잡도
O(NlogN) - 정렬 O(NlogN), 반복문 O(N)
"""

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    
    return participant[-1]

""" 
- 예시 1
참가자 = [A, B, C, D]
완주자 = [A, C, D]
-> B와 C의 비교에서 일치하지 므로 B를 반환한다.

- 예시 2
참가자 = [A, B, C, D]
완주자 = [A, B, C]
-> 반복문 내에서 판별이 안됐으므로 참가자의 마지막인 D가 완주하지 못한 경우 이므로 D를 반환한다
"""

느낀점

해시 함수의 대한 공부가 더 필요해 보인다.