프로그래머스 해시 - 완주하지 못한 선수

🔸 문제 접근 방식

❗ 풀이 성공, 시간 초과

1. participant, completion을 Queue에 넣는다.
2. completion을 꺼내 participant에 있으면 participant에서 제거한다.
3. completion 요소가 없어질때까지 반복하고 남아있는 participant를 반환한다.

→ 이 문제의 경우 답을 구할 수는 있지만, 효율성 문제가 있었다.

시간복잡도가 O(N^2)일 경우 통과할 수 없다.

⭕ 시간 초과 해결

best_solution1, 2로 풀이 시 효율성 문제를 통과할 수 있었다.

best_solution1의 경우, 정렬 후 최대 $10^5$번 비교를 수행하기 때문에 O(N)만 수행하면 된다.

best_solution2의 경우 해시를 사용한 풀이방식으로 시간 단축에 효과적이었다.

💧 Sourece Code

# 2021.09.05 최신풀이 - hash_map 사용
from collections import defaultdict

def solution(participant, completion):
    answer = ''
    start = defaultdict(int)
    
    for p in participant:
        start[p] += 1
    
    for c in completion:
        start[c] -= 1
    
    for k, v in start.items():
        if v != 0:
            answer = k  
    
    return answer
=========================================================================
from collections import deque

def solution(participant, completion):
    '''
    Notes: 
    - 해당 풀이는 deque 사용 시 시간초과 문제가 발생하는 문제가 있었다.
    - 시간복잡도 계산 시 O(N^2)일 경우 통과가 안되도록 설계되어 있는 듯 하다.

        1. participant, completion을 Queue에 넣는다.
        2. completion을 꺼내 participant에 있으면 participant에서 제거한다.
        3. completion 요소가 없어질때까지 반복하고 남아있는 participant를 반환한다.

    Args:
        participant (list): 참가자 리스트
        completion (list): 완주자 리스트

    Returns:
        answer (str): 완주하지 못한 참가자 이름

    '''

    answer = ''
    participant = deque(participant)
    completion = deque(completion)

    while completion:
        one = completion.popleft()
        if one in participant:
            participant.remove(one)

    answer = list(participant)
    return answer[0]

def best_solution1(participant, completion):
    answer = ''
    participant.sort()
    completion.sort()

    for p, c in zip(participant, completion):
        if p != c:
            return p

    return participant[-1]

def best_solution2(participant, completion):
    answer = '' 
    temp = 0 
    dic = {}
    for part in participant: 
        dic[hash(part)] = part 
        temp += int(hash(part)) 

    for com in completion: 
        temp -= hash(com)

    answer = dic[temp]
    return answer

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
print(solution(participant, completion))