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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=python3

프로그래머스

 

해설

시간복잡도로 인해 개자 작성하던 코드의 시간 복잡도가 \( O(n^2) \)로 수렴하여 Timeout fail이 발생하였다. 이를 해결하기 위해 Counter 함수 사용으로 \( O(n) \)으로 수렴하도록 하는 것이 핵심이었다.

 

Solution 1.

collections 패키지를 이용하여 Counter 메소드를 활용해보았다.

 

import collections

def solution(participant, completion):
    return (collections.Counter(participant) - collections.Counter(completion)).popitem()[0]

 

 

Solution 2.

패키지 사용 없이도 풀어보았다. \( O(n log n) \)의 시간복잡도이지만 \( O(n^2) \)보단 확연히 개선되었기 때문에 통과할 수 있었다.

 

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for p, c in zip(participant, completion):
        if p != c:
            return p
    
    return participant[-1]  # 모든 항목이 동일하면 마지막 항목이 남은 참가자