[프로그래머스 스터디] 완주하지 못한 선수 - Python(zip 함수, Counter함수)

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

...

프로그래머스 알고리즘 스터디를 수강하면서 사전테스트에 나왔던 문제.
세션 도중 강사님이 보여주신 새로운 파이썬 함수를 배웠고 기억하고자 글을 남긴다.

문제 해설

participant, completion 두 리스트 차이를 비교해 completion에는 있지만 participant에 없는 한 사람을 찾는 문제. 단 동명이인이 있기 때문에 그 부분도 신경써주어야했다.

첫번째 풀이

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

간단하게 완주한 사람을 참가자에서 지워주게되면 결과는 모두 맞지만 효율성에서 시간초과가 나타난다. remove 함수의 시간복잡도는 O(N)으로 사실상 위 로직은 O(n^2)의 시간복잡도를 가지게 된다.

해결 풀이

def solution(participant, completion):
    player = sorted(participant)
    comp = sorted(completion)

    for i in range(len(comp)):
        if player[i] != comp[i]:
            return player[i]

    return player[-1]

시간초과를 피하기 위해 O(n log n)시간복잡도를 가진 정렬을 해주었고 completion 리스트의 길이 만큼 for문을 돌며 participant에 다르다면 그 때 return, for문 마지막까지 돌았다는 것은 participant에 마지막에 남은 선수가 완주하지 못한것이므로 그때 마지막 선수를 return한다.

새로 배운 해결방안

zip함수를 활용한 해결방안

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

zip이라는 함수를 처음 배웠다. zip은 리스트끼리의 같은 인덱스의 값들을 서로 튜플형태로 묶어준다.

입력값 -> 	['eden', 'kiki', 'leo'] ['eden', 'kiki']
zip함수 출력값 -> [('eden', 'eden'), ('kiki', 'kiki')]

만약에 다른 선수가 등장하면 그게 완주하지 못한 사람이고 마지막까지 없다면 마지막 선수가 완주하지 못한 사람.

Counter함수를 활용한 해결방안

from collections import Counter

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

Counter함수라는 것도 처음 배울 수 있었다. 우선 Counter의 결과값부터 보자.

Counter(participant) -> 
Counter({'leo': 1, 'kiki': 1, 'eden': 1})
Counter(completion) ->
Counter({'eden': 1, 'kiki': 1})

Counter라는 함수는 리스트에서 각각의 요소의 개수를 세서 딕셔너리 형태로 가지고 있는 아주 편리한 함수이다. 더욱 편리한 점은 "-"연산이 가능해서 연산값이 0이 된 순간 값이 해제되기 때문에 마지막에 남은 값이 완주하지 못한 선수가 된다.

...

파이썬에는 편리한 함수가 정말 많아서 이런 함수들을 잘 알고있는다면 앞으로의 알고리즘 문제를 푸는데 있어서 많은 도움이 될 것이다.