프로그래머스 level 1 완주하지 못한 선수(collections.counter), 해시

완주하지 못한 선수

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

사고 과정

def solution(participant, completion):
    if (i in participant) and ( i not in completion):
        return i

무식하면 용감하다고 이런 생각을 했다. 물론 작동하지 않는다.
participant - completion하면 되는거 아닌가?! 라고도 생각했다.

모범 답안

import collections 

def solution(p, c): 
    p.sort() 
    c.sort() 
    ans = collections.Counter(p) - collections.Counter(c) 
    return list(ans)[0]

그런데 그것이 실제로 일어났습니다..!
collections 모듈의 Counter 클래스는 dictionary를 확장한 클래스로, 데이터의 개수를 효과적으로 셀 수 있는 기능을 제공한다.
Counter(participant)는 participant의 각 요소들과 그 개수를 짝지어서 가지고 있기 때문에, Counter(completion)을 빼 주게 되면 겹치는 요소들의 개수를 빼서 결과적으로 answer에는 단 하나의 이름(key)과 1(value)만 남게 된다.

모범 답안2

import collections

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

설명 출처 : 오지님의 블로그

모범 답안 출처: 개발개발 울었다

주요 포인트 및 생각해볼 점

해쉬(Hash): 임의 값을 고정 길이로 변환하는 것

해쉬 구조란?
키(Key)와 값(Value)쌍으로 이루어진 데이터 구조를 의미한다. Key를 이용하여 데이터를 찾으므로, 속도를 빠르게 만드는 구조이다.

파이썬에서는 딕셔너리(Dictionary) 타입이 해쉬 테이블과 같은 구조이다.
기본적으로는, 배열로 미리 Hash Table 크기만큼 생성해서 사용한다. 공간은 많이 사용하지만, 시간은 빠르다는 장점이 있다.

검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용된다.

인터넷의 답안을 복사해서 붙여넣었더니 프로그래머스에서 완료처리가 되지 않았다. 나중에 다시 보고 직접 collection을 이용해서 짜봐야겠다.

출처 : DAVINCI - AI