[Algorithm🧬] 완주하지 못한 선수

문제 / 풀이.py

풀이 1. 처음에는 for문을 박박 돌렸다.

def solution(participant, completion):
    answer = ''
    count = 0
    copy = participant

# 참가자 배열을 끝에부터 돌려서
    for i in range(len(participant)-1, -1, -1):
        if len(completion) == 0:
            break
        # completion에 participant 가 있으면 참가자에서 삭제하는 방식으로 진행을 했다.
        # 그러면 맨 마지막에 통과 못 한 한 사람만 남으니까!
        if participant[i] in completion:
            completion.remove(participant[i])
            copy.pop(i)
            
    answer = copy[0]
    
    return answer

근데 효율성에서 전부 실패했다. 아무래도 participant 수를 n이라고 하면, completion 은 n-1 이라 O(n^2)이 되었을테니깐...

for i in range(len(participant)-1, -1, -1): # n
	if participant[i] in completion: # n-1

그래서 dictionary 를 사용해서 다시 풀었다.

def solution(participant, completion):
    answer = ''

    count = 0
    dict = {}
    
    for person in participant:
        dict[person] = 0

    for person in participant:
        dict[person] += 1
    
    for completed_person in completion:
        dict[completed_person] -= 1
        
    for key in dict:
        if dict[key] == 1:
            answer = key
        
    return answer