완주하지 못한 선수

문제

 

문제

 

처음 작성한 코드(dict, hash X) // 효율성 체크 Non Pass

def solution(participant, completion):
     _par = [i for i in participant]
     _com = [i for i in completion]
     result = []
     for value in _par:
         if value not in _com:
             result.append(value)
         else:
             _com.pop(_com.index(value))
     return ''.join(result)

 

두번째 작성한 코드(dict O) // 효율성 체크 Non Pass

def solution(participant, completion):
    _par = {x:participant.count(x) for x in participant}
    _com = {x:completion.count(x) for x in completion}
    for key in _com.keys():
        _par[key]-=_com[key]
    for key in _par.keys():
        if _par[key]!=0: 
            result = key
            break
    return result

_par, _com에 값을 넣는 과정 중 count(x)와 for문에서 모두 O(n) 만큼 소요, 즉 O(n^2) 소요 -> 효율성 나쁨

 

세번째 작성한 코드(dict O) // 효율성 체크 Pass

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

 

 

코드 리뷰 후(hash O)

def solution(participant, completion):
    temp = 0
    dic = {}
    for p in participant:
        dic[hash(p)] = p
        temp += hash(p)
    for c in completion:
        temp -= hash(c)
    return dic[temp]

1. participant의 원소(참가자 이름)에 따른 hash 값을 key로 하고 원소(참가자 이름)를 value로 하는 dic을 생성

 -> hash값 계속 변화

2. 참가자 리스트를 돌면서 temp에 참가자 이름에 따른 hash값을 더해준다.

3. 완주자 리스트를 돌면서 temp에서 완주자 이름에 따른 hash값을 빼준다.

4. 그렇게 되면 하나의 hash 값만 남을 것이다.

5. 그 hash 값에 대한 value(참가자 이름)를 return 한다.

 

 

깨달은 점

1. dictionary는 dict() 또는 {} 요렇게 초기화할 수 있고, key:value 이렇게 구성된다. dict[key] 하면 value를 직접 접근할 수 있어서 O(1)의 시간이 걸린다고 한다.

2. collections라는 라이브러리를 알아냈다. collections의 Counter()는 "key:key의 갯수" 이렇게 정리해준다.

3. Counter()는 뺄셈 연산이 가능하다. dict의 item 갯수가 다르더라도 가능하다.

4. hash()의 사용법을 알게되었다. 코드 밑에 설명을 썼다.