#4 완주하지 못한 선수:

date posted: 2020-04-15

오늘의 TMI

1. B&O e8 1세대가 고장났지만 전여자친구가 사줬던거라 보증서 없음.
2. B&O e8 3세대를 인터넷에서 사려는데 정품일까 걱정.
3. 내일 퇴근하고 백화점에서 들러볼거.
4. TMI 쓰는 파트가 가장 재밌음.

코딩 풀이 시작

해시 문제중 하나이기때문에 아마 메모리를 최대한 줄이는것에 신경을 써야할듯합니다.

# 1 시도

def solution(participant, completion):
    for c in completion:
        participant.remove(c)
        
    return participant[0]

• 정확성 테스트는 모두 통과 했으나 효율성 테스트는 다 실패 하였습니다.
• completion 의 선수는 participant 선수들보다 한명이 적으니 저희의 time complexity 는 O(n) = n 입니다.
• 제생각엔 O(n) = n 이 아니라 remove 할때 다시 선수이름을 participants 그륩에서 linear 타임으로 찾아야 하기때문에 O(n) = n^2 인거 같네요.

# 2 시도

• 아래코드는 {"leo":1, "kiki":0, "eden":0} 이런식으로 table이 만들어 집니다. leo의 카운트가 남았기때문에 leo 가 완주 하지 못했는데. 쟤만 딱 짚어주는 방법을 고민.

from collections import defaultdict
    table = defaultdict(int)
    for p in participants:
        table[p] += 1
    for c in completion:
        table[c] -= 1

• {1: "leo", "kiki":0} 이런식으로 바꾸고 table[1] 을 return 하도록 해보자.

# 3 시도

• 각 선수마다 해쉬값을 만들어주고 해쉬값을 넣으면 선수이름이 나오는 테이블을 만들어야 한다.
• ex: leo -> hash(leo) = x -> hash_table[x] = leo

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

• 각 선수당 해쉬값을 정해주는 python의 hash function 이 있다. hash("leo") = 해쉬값
• 선수이름마다 hash 값을 받으면 hash_table[해쉬값] = 선수이름 을 넣어 hash_table을 만든다.
• 계속 hashkey 값에 선수의 hashkey 값을 더해주고 빼서 남은 hashkey값을 hash_table 에 넣어주면 그 남은값의 선수가 나올것.

물론 해쉬 함수를 직접 만들면 더 좋겟지만 그래도 이것이 가장 hash table 를 잘 이해하고 잘 사용하는것 같다.

# 1 alternative 풀이

• Counter["a", "a","b", "c"] --> {a:2, b:1, c:1}, 리스트에 있는 문자를 count 한 dictionary 만듬.
• {a:2, b:1, c:1} - {a:1, b:1} = {a:1, c:1}. 이런식으로 빼기도 가능
• 테이블을 만들라면 하나씩 loop 해야하는거 아닌가? 도대체 어떤식으로 만드는 건지 알수 없으니 직접 만들어 본다. # 2 시도 에서 보세요.

from collections import Counter

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