[프로그래머스] 완주하지 못한 선수 - python

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

프로그래머스

설계 방법

completion 돌면서 participant에 i가 있으면 completion 배열에서 i 지워주고, 마지막 남은 participant를 반환해주면 된다고 생각했음

근데 이렇게 하면 시간복잡도가 O(n^2) 이기 때문에 시간초과발생

 

문득 python 내장 sort() 함수가 O(nlogN)인 게 기억났음

내장함수 사용해서 정렬한 뒤, 순서대로 빼면 되겠구나 생각함

코드

시간초과

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

나의 풀이코드

from collections import deque
def solution(participant, completion):
    participant.sort()
    completion.sort()
    completion.append('0')
    for i in range(len(participant)):
        if participant[i] != completion[i]:
            return participant[i]

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

해싱 알고리즘 사용 코드

def solution(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

 

참고

Python의 sort() 내장 함수의 시간 복잡도는 보통 O(n log n)임

Python의 sort() 함수는 Timsort라는 알고리즘을 기반으로 동작함

Timsort는 병합 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)의 조합으로 구성되어 있으며, 최선의 경우에는 O(n)의 시간 복잡도를 가지지만, 일반적으로 평균적인 경우에는 O(n log n)의 시간 복잡도를 가짐

Timsort는 데이터를 여러 부분으로 나누고, 각 부분에 대해 정렬 후 병합하는 과정을 반복하여 전체 리스트를 정렬함. 정렬된 작은 부분 리스트들을 병합하는데 필요한 시간이 O(n)이고, 분할하는 과정이 O(log n)번 발생하므로, 최종적으로 평균적인 시간 복잡도는 O(n log n)이 되는 것 

하지만, 리스트의 크기가 작은 경우에는 삽입 정렬과 유사한 작은 크기의 부분 리스트를 정렬하는 과정이 더 빠르기 때문에, 최선의 경우에는 O(n)의 성능을 보여줄 수 있음