📌 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42576

📌 풀이

코드

def solution(participant, completion):
    # { key - 선수 이름 : value - 동명이인 수 }인 딕셔너리 만들기
    p = {name : 0 for name in participant}
    for name in participant :
        p[name] += 1
        
    # 완주한 선수가 나오면 인원 빼기
    for c in completion :
        p[c] -= 1
    
    # 딕셔너리 value가 0보다 크다는 것은 완주를 못한 선수라는 뜻임
    for key, val in p.items() :
        if val > 0 :
            return key

설명

처음 작성한 코드는 아래와 같다.

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

이 코드도 동작은 하는데, 시간초과가 뜬다. 시간 복잡도가 $O(n^2)$이기 떄문이다. remove가 메소드기 때문에 한 줄로 쓰인거지 내부 동작하는 걸 보면 리스트에서 원소를 하나하나 돌기 때문에 for문이 하나 더 있는 것과 같다.

그래서 이를 해결하기 위해 위와 같이 코드를 수정했다. { 선수 이름 : 동명이인 수 } 형태인 딕셔너리를 만들고 완주한 선수를 빼는 식으로 동작한다. 이 코드의 시간 복잡도를 보면 for문이 네 개나 있긴 하지만 각각 독립되어있으므로 $O(n)$이다.