1일차, 완주하지 못한 선수

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

문제를 보고 든 생각

풀어봤던 문제다.

나의 아이디어

for문을 돌려가면서 참가자 리스트 요소들의 해시값을 모두 더해놓은 다음, 완주자 리스트 요소들의 해시값을 뺀다.

그러면 이름 한 개의 해시값만 남게 되겠지?

나의 코드

def solution(participant, completion):
    hash_sum = 0
    
    for name in participant:
        hash_sum += hash(name)
    for com in completion:
        hash_sum -= hash(com)
        participant.remove(com)
    
    return participant[0]

코드의 결과

총점 100점 중 정확성 테스트만 통과하고 효율성 테스트는 모조리 탈락했다.

드는 생각

도대체 왜 저렇게 제출을 했는지 지금도 이해가 안 간다. 분명히 해시값을 쓰자고 해놓고 갑자기 remove를 하고 있다. 그럴 거면 for문 하나에 remove만 쓰면 되는 건데 왜 갑자기 remove를 썼는지 모르겠다.

개선

def solution(participant, completion):
    hash_sum = 0
    
    for name in participant:
        hash_sum += hash(name)
    for com in completion:
        hash_sum -= hash(com)
    for name in participant:
        if hash_sum == hash(name):
            return name

위의 코드를 사용하면 정확성 테스트와 효율성 테스트를 모두 통과할 수 있다.

그리고 시간복잡도 관련하여 멘토님께 질문하면서 알게 된 사실인데, python에서 hash함수는 거의 쓸 일이 없다고 한다.

강의에서 배운 것

강사님께서는 이 문제는 해시 테이블이라는 자료구조를 사용하여 풀면 되는 문제라고 말씀해주셨다.

해시테이블은 자료의 데이터가 키 값이 되고 테이블 내에서는 인덱스의 역할을 한다. 그래서 원하는 데이터를 빠르게 찾을 수 있는 자료구조라고 설명해주셨고 정확히는 탐색하는 데에 있어서 상수 시간의 시간복잡도를 가진다고 한다.

강의를 통해 알게 된 풀이

# 해시테이블을 위한 dictionary
data = {}

for name in participant:
    data[name] = data.get(name, 0) + 1

for com in completion:
    data[com] -= 1
    
answer = [k for k, v in data.items() if v > 0]
print(answer[0])

1. 해시테이블에 리스트 요소를 key값으로 하여 요소를 넣어준다. 이때 value값은 get 메소드를 이용하여 넣어준다.

data.get(key값, 이 key값에 대응하는 value값이 없다면 넣을 value값) + 1(이미 존재하는 key라면 value에 더해줄 값)

 

2. 완주자들의 데이터가 key값이 되어 테이블 안에 똑같은 key값이 있다면 그 key값의 value에 -1을 해준다.

 

3. 참가자보다 완주자는 항상 1명이 많으므로 무조건 value가 1인 key값이 하나 있을 것이다. 그 key값을 answer에 저장한다.

 

추가+

나의 첫 풀이와 나의 첫 풀이를 개선한 풀이 간의 시간복잡도 차이가 궁금해서 질문을 드렸다.

나는 분명히 두 코드 모두 O(N)을 의도하고 코드를 적었는데 한 코드는 통과하고 한 코드는 효율성 테스트에서 모두 떨어졌기에 너무나도 시간복잡도 차이에 대해 궁금해졌었다.

혹시나 하는 마음으로 첫 코드에 적혀있는 remove()가 그 차이를 만들었나 싶긴 했었는데, 역시나였다.

remove()는 시간복잡도 O(N)을 차지한다. O(N)의 시간복잡도를 가지는 for문 안에서 remove가 계속 도니 O(N^2)의 시간복잡도를 갖게 되는 코드가 되어 버린 것이다.

 

import time

def solution(participants, completion):
    
    t_remove = 0
    t_start = time.time()
    hash_sum = 0
    for name in participants:
        hash_sum += hash(name)
    for com in completion:
        hash_sum -= hash(com)
        t_remove_start = time.time()
        participants.remove(com)
        t_remove += time.time() - t_remove_start
    t_end = time.time()
    
    print(t_remove * 100 / (t_end-t_start))
        
    return participants[0]

participant = ['a']*100001
completion = ['a']*100000
solution(participant, completion)

 

멘토님이 작성해주신 코드이며 remove()가 이 코드 안에서 어느 정도로 시간을 잡아먹고 있는지 확인시켜준다.

확인 결과로 약 96퍼센트의 시간복잡도를 remove() 혼자 해먹는 걸 알아볼 수 있다.