중복이 있는 participant 리스트와,
그보다 1만큼 적고 중복이 없는 completion 리스트가 주어질 때,
-> completion에 없는 participant를 구하라. ( 딱 1개 )
def solution(participant, completion):
spar = sorted(participant)
scom = sorted(completion)
for i in range(len(scom)-1):
temp1 = spar.pop()
temp2 = scom.pop()
if temp1 != temp2:
return temp1
# 정확성 테스트 2는 정렬했을 때, 마지막으로 participant 가 하나 남았을 때.
# a a b b c // a b b c
# a //
return spar.pop()
고민했지만, 구현하지 못한 내용
p_set = set(participant)
c_set = set(completion)
p_set - c_set 의 값을 return 하고 싶지만, participant는 중복이 있어서 불가.
def solution(participant, completion):
participant_set = set(participant)
completion_set = set(completion)
result = list(participant_set - completion_set)
if result !=[]:
return result[0]
else:
for c in completion:
a=completion.count(c)
b=participant.count(c)
if(a != b):
return c
return None
2번의 내용에서 중복에 대한 것을, count(c)로 갯수를 세어 다른 경우 return 하였다.
나중에 중복을 만날 경우, "수" 로 비교가 가능하다는 것을 생각해보자.
O(1) 상수 시간의 접근을 위해 Hash Key를 사용하는 Dictionary 자료구조를 사용한다.
def solution(participant, completion):
d = {}
for x in participant:
# d.get(x) 를 한 값이 없으면 (Falsy 하면) 0을 넣고, 값이 있으면 1을 넣는다.
d[x] = d.get(x, 0) + 1
for x in completion:
d[x] -= 1
# v가 0보다 큰, 즉 위의 completion 반복문에서 포함되지 않은 아이템의 key를 담는다.
ans = [k for k, v in d.items() if v > 0]
return ans[0]
순환문 1) participant 배열의 길이(n)만큼
순환문 2) completion 배열의 길이(n)만큼
ans =[ ... ] ) d의 길이(n)만큼.
-> linear time
.sort() 를 사용하면,
-> O(NlogN) 이 되므로 Hash를 사용한 풀이가 더 성능적으로 우수하다고 볼 수 있다.