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

문제: 완주하지 못한 선수

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

• 내 풀이

- 순서대로 정렬해서 completion값과 비교하는 도중 틀린 값이 나오는 경우/ 비교해도 나오지 않는 경우

두 가지로 나눠서 리턴 값 지정

 

def solution(participant,completion):
    participant.sort()
    completion.sort()
    for i in range(len(participant)-1):
        if participant[i]!=completion[i]:
            return participant[i]
    return participant[-1]

 

• 다른 사람 풀이

1. 가장 효율적인 풀이

- collection 모듈의 Counter 클래스 사용

- Counter 클래스는 iterable 객체(list, dict, set, str, bytes, tuple, range)와 같은 반복 가능한 객체의 요소를 카운트

 → 각각의 빈도 값을 {요소:빈도} 형태인 해쉬 테이블형태(카운터 객체)로 반환

import collections


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

 

2. 해시 함수를 이용한 풀이

• 해싱
  •  해싱이란 많은 양의 데이터를 integer와 같이 작은 양의 데이터로 반환해주는 알고리즘
  • 파이썬에서는 딕셔너리{Key:Value} 로 이용한다.
• hash(part) 를 Key로 이용해서 딕셔너리에 삽입

출처: 위키피디아 '해시'

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

 

-해시함수: String을 기반으로 정보 기록/관리해야할 때 사용

https://www.youtube.com/watch?v=zFL29ydL9D8