문제

완주하지 못한 선수

코드

성공

def solution(participant, completion):
    answer = ''
    d_part = dict()
    for p in participant:
        if p in d_part.keys():
            d_part[p] += 1
        else:
            d_part[p] = 1
            
    for p in completion:
        d_part[p] -= 1
    
    for key in d_part.keys():
        if d_part[key] != 0:
            return key

실패

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

깨달은 점

효율성 테스트에서 실패와 성공이 갈렸다. 시간 복잡도에서 문제가 있었던 듯 하다.

GPT 4의 해설

두 코드 모두 파이썬의 리스트와 딕셔너리를 사용하고 있습니다. 이들의 공간 복잡도는 입력 크기에 비례합니다. 즉, O(n)의 공간 복잡도를 가집니다. 여기서 n은 participant의 길이입니다.

하지만 두 코드 사이에는 중요한 차이점이 있습니다.

첫 번째 코드는 딕셔너리를 사용합니다. 딕셔너리는 키-값 쌍을 저장하므로, participant의 각 요소를 키로, 그 요소의 등장 횟수를 값으로 저장합니다. 따라서 participant의 모든 요소를 저장하므로 공간 복잡도는 O(n)입니다.

두 번째 코드는 participant 리스트에서 completion 리스트의 요소를 제거합니다. 이 경우, participant 리스트는 completion 리스트의 요소를 제거한 후에도 여전히 메모리에 남아 있습니다. 따라서 이 경우에도 공간 복잡도는 O(n)입니다.

그러나 두 번째 코드는 remove 연산을 사용하므로, 이 연산은 리스트의 길이에 비례하는 시간이 걸립니다. 따라서 두 번째 코드의 시간 복잡도는 O(n^2)입니다. 반면, 첫 번째 코드는 딕셔너리를 사용하므로 키를 통한 접근, 추가, 삭제 등의 연산은 평균적으로 O(1)의 시간 복잡도를 가집니다. 따라서 첫 번째 코드가 더 효율적입니다.