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

Hash를 활용한 풀이 또한 정리하고자 한다.

programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

나의 풀이

정렬을 활용하여 풀었다.

단 1명만, 완주하지 못했으므로, 참가자와 완주자 배열을 사전순으로 정렬하면 처음으로 어긋났을 때, 그 시점의 참가자가 완주하지 못한 사람일 것이다.

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

기본적으로 정렬이 들어가기에 시간 복잡도가 O(nlogn)이다.

 

해시를 활용한 풀이

해시를 활용한 풀이는 다음과 같다.

# 해시 풀이법
# 플이 : 상수시간만큼 진행된다.
# 알고리즘의 복잡도 : O(n)
def soultion(participant, completion):
    d = {}
    for x in partinipant:
        # get 메서드는?
        d[x] = d.get(x,0)+1
    for x in completion:
        d[x] -= 1
    dnf = [k for k, v in d.items() if v > 0] # key만 담긴다.
    answer = dnf[0]
    return answer

특정 이름을 참가자가 몇번 참가하는지 센 후, 완주할때마다 1씩 뺀다. 파이썬의 dictionary를 통해 이를 구현할 수 있다.

이 경우는 시간복잡도가 O(n)이므로 시간복잡도 면에서 더 우수한 풀이라 볼 수 있다.