[Algorithm] 완주하지 못한 선수

해결 과정

처음 생각: 차집합 해주면 되지 않나 생각했음. 근데, 중복된 선수가 있으니까 차집합 못씀. (근데 이런 비슷한 개념이라고 생각했음.)

무조건 participant는 completion보다 1개가 더 많을거고. 그럼 for문 다 돌면서 없는 것 빼주면 되겠다 생각함.

처음엔 completion를 하나씩 돌면서 participant의 첫번째 index 원소를 빼주는 방식으로 구현했는데, 정답은 나오지만 시간초과가 남.

그래서 결국 각각 sort 해주고, for문 하나씩 돌면서 다른 것 있으면 바로 출력하는 방식으로 구현함. 해결.

 

나의 풀이

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i, j in zip(participant, completion):
        if i == j:
            continue
        else:
            return i
    return participant[-1]

리팩토링

참고) zip은 list의 개수가 서로 다르면 제일 작은 list의 개수까지만 zip해줌.

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

시간 초과 난 풀이

def solution(participant, completion):
    for finisher in completion:
        del participant[participant.index(finisher)]
    return participant[0]

+ 2022.02.16 다른 풀이 - 더 어렵게 푼거 같기도,, 효율성은 더 좋아진 듯

from collections import Counter
def solution(participant, completion):
    answer = ''
    if len(set(participant)) == len(set(completion)):
        pCounter = Counter(participant)
        cCounter = Counter(completion)
        for key, value in pCounter.items():
            if value == 1:
                continue
            else:
                if value != cCounter[key]:
                    answer = key
                    break
    else:
        answer = list(set(participant) - set(completion))[0]
    return answer

다른 풀이

collections의 Counter 사용

import collections

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

같은 원소의 개수를 세준 Counter에서 -를 사용. 

 

hash() 사용

각 이름에 hash() 결과를 key로 가지는 dictionary를 만든다.

participant 끼리 모두 더하고, completion 끼리 모두 더해서 빼주면 hash값 하나가 나올 텐데, 그 hash값을 key로 갖는 value를 출력해주고 있다. (결국 다 도는데)

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

    return dic[temp]