프로그래머스) 해시/완주하지 못한 선수

내 풀이

def solution(participant, completion):
    answer = ''
    for i in completion:
        if i in participant:
            participant.remove(i)
    answer += participant[0]

    return answer

정확성 테스트는 다 맞게 나오는데 효율성 테스트가 5개 다 실행초과로 실패했다.. remove 때문에 그런 것 같아서 구글링을 해보니 맞았다.
remove() 는 처음부터 탐색하는 비효율적인 함수여서 O(n^2) 의 시간복잡도를 갖게되어 효율성 점수가 0점인 것이었다. 보통 O(n) 정도로 풀이해야 한다고 한다.

다시 푼 풀이)
구글링을 해보니 해시함수는 key, value 를 사용해서 딕셔너리로 풀이해야한다고 되어있어서 다시 풀이했다.

def solution(participant, completion):
    answer = ''
    andict = {}
    for i in participant:
        if i in andict.keys():
            andict[i] += 1
        else:
            andict[i] = 1
    for j in completion:
        andict[j] -= 1
    for k in andict.keys():
        if andict[k] != 0:
            answer += k
            break
    return answer 

이렇게 하니 정확성, 효율성 모두 만점이 나왔다. 해시함수가 빈도수가 가장 많다고 되어있으니 빨리 모두 풀어봐야겠다.

다른 풀이 1)

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

sort를 사용해서 풀이한 것이 아이디어가 좋다.

다른 풀이 2) 출제자의 의도와 맞는 해시함수 풀이이다.

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

다른 풀이 3) 간단한 풀이

import collections 
	def solution(participant, completion): 
    	answer = collections.Counter(participant) -collections.Counter(completion) 
        return list(answer.keys())[0]