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

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

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

문제 설명

· 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 반환

· 완주하지 못한 선수는 항상 한 명

· 참가자 중에는 동명이인이 포함될 수 있다.

정리하면 participant 중 completion에 없는 참가자 한 명을 구하는 것.

접근 방법

· 동명이인이 있을 수 있으므로 set을 통한 intersecion은 제외

· participant, completion를 정렬한 후, 두 배열이 달라지는 인덱스의 participant의 문자열을 반환

알고리즘 설계 및 구현

def solution(participant, completion):
    # 참가자와 완주자 명단을 정렬
    participant.sort()
    completion.sort()
    
    # 정렬된 두 리스트를 순회하며 비교
    for p, c in zip(participant, completion):
        if p != c:
            return p  # 참가자와 완주자가 다르면 해당 참가자를 반환
    
    # for loop에서 찾아내지 못했을 경우, 마지막 참가자가 완주하지 못한 선수
    return participant[-1]

결과

최적화 및 개선 방안

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

· participant, completion를 정렬한다면 O(N log N) 복잡도를 가지게 되는데, collections.Counter를 이용한다면 O(N) 복잡도를 가지므로 효율적