코딩테스트 연습/프로그래머스

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

슈퍼짱짱 2022. 3. 11. 14:45
반응형

(Python 코딩테스트 연습) Programmers 완주하지 못한 선수 파이썬으로 풀어보기

 

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

 

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

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수

programmers.co.kr

 

 


Solution

 

from collections import Counter

def solution(participant, completion):
    result = list(set(participant)-set(completion))
    if len(result) == 0 :
        p = dict(Counter(participant))
        c = dict(Counter(completion))
        d = {key: p[key] - c.get(key, 0) for key in c}
        result = list([item for item in d if d[item]>0])
    return result[0]

 


처음에는 for문으로 completion의 item을 participant 리스트에서 하나씩 꺼내도록 코드를 짰다.

 

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

 

그랬더니 정확성 테스트는 모두 통과했으나, 효율성 테스트는 통과하지 못했다.

즉, for문으로 하는 것이 아니라 vectorizing하여 한 번에 계산해야 한다.

 

이를 해결하기 위해 collections 모듈의 Counter 함수를 사용했다.

 

Counter

 

객체를 세기 위한 dict 서브 클래스.

요소가 딕셔너리 키로 저장되고 개수가 딕셔너리 값으로 저장됨.

 

예)

 

동명이인이 없다면 result = list(set(participant)-set(completion)) 만으로 해결가능하다.

하지만, 동명이인이 있다면 해당결과는 빈 리스트가 return된다.

 

따라서 동명이인이 존재할 경우를 고려해주어야한다.

 

본 문제에 예시는 동명이인이 한 명일때만 있으나, 동명이인이 두 명일때를 꼭 고려해 주어야한다.

 

동명이인이 한 명일 때는 다음과 같이 Counter(participant)의 결과 값이 1명보다 많은 경우를 return해주면 된다.

 

result = list(set(participant)-set(completion))
if len(result) == 0 :
    d = Counter(participant)
    result = list([item for item in d if d[item]>1])

 

하지만, 동명이인이 다음과 같이 두 명 이상인 경우라면 result의 결과가 두 명이 이상이 된다.

 

participant =["mislav", "stanko", "mislav", "stanko"]
completion = ["stanko", "mislav", "mislav"]

 

 

따라서 제시한 solution처럼 participant와 completion 모두 Counter로 개수를 세어주고, 같은 key에 해당하는 value를 빼주는 형태로 코드를 짰다. 

 


다른 사람의 풀이

 

다른사람의 풀이를 보니 같은 컨셉인데 훨씬 간단하게 구현되어있다.

 

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

 

 

동명이인인지 아닌지 if문으로 확인할 필요없이 바로 결과로 뽑을 수 있으며,

Counter 객체를 굳이 dict으로 바꿔주지 않고, 바로 - 연산을 해주었다.

 


 

collections 모듈을 불러오지 않고 직접 구현한 코드도 있다.

직접 hash함수를 사용하는 경우이다.

 

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

 

hash

 

특정 값을 식별하는 고정 크기의 정수.

각 값에는 고유한 hash가 있어야 하므로, 동일한 값에 대해서는 동일한 hash를 얻게 됨.

 

예)

 

"A"와 "B"는 다른 값이므로 다른 hash값을 얻으며, 동인한 "A"라는 값에 대해서는 동일한 hash를 갖음.

 

위 코드에 for문 안의 모든 값을 print 해보면 다음과 같다.

 

participant =["mislav", "stanko", "mislav", "stanko"]
completion = ["stanko", "mislav", "mislav"]

 

 

 

즉, 같은 "mislav"라는 이름에 대해서는 participant 리스트에 있을 때나, completion 리스트에 있을 때나 같은 hash값을 가진다는 hash의 특징을 활용하여 구현한 코드이다.

 

 

 

반응형