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

 

문제 링크

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

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

 

나의 풀이

일반적으로 구현방식말고 "해시"라서 최대한 dic을 활용해서 풀려고 노력해봤다. 확실히 효율성, 시간복잡도 측면에서 key값을 활용한 hash 방법이 좋은 것 같다!!

1. hash는 모든 값을 숫자로? 처리 
2. hash 값을 key값으로 갖고 이름을 value값으로 갖는 딕셔너리를 생성
3. participant 에 있는 모든 이름의 hash값을 hash_num이라는 변수에 더해준다.
4. participant에 있지만 completion에는 없는 이름을 찾아야 하기에 participant에 있는 모든 값을 더한 hash_num에서 completion에 있는 이름들을 빼준다.
5. 그럼 hash_num에 남은 숫자는 완주하지 못한 선수의 이름을value값으로 갖는 key값이 될것

def solution(participant, completion):
    dic = {}
    hash_num = 0
    for p in participant:
        dic[hash(p)] = p #hash값:key, p:value
        hash_num +=  int(hash(p))
    for c in completion:
        hash_num -= int(hash(c))
    
    return dic[hash_num]

 

다른사람풀이

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

프로그래머스

해시 알고리즘을 사용해서 풀려고 노력했더니 나랑 비슷하게 해시알고리즘을 사용해서 푼 사용자가 많았다. 뿌듯했다 ^0^ 그리고 대부분 이런 문제는 sort() 해서 효율을 높인다고 한다. sort하면 효율이 높아지나...?

이외에도 zip함수, Counter함수를 이용해서 푼 풀이방법이 효율성적인 측면에서 높게 점수를 높게 받았다. 아무리 해시 알고리즘 문제지만 역시 접근하는 방법으 너무 많다!

Counter 함수 이용

import collections


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

 

zip 함수 이용

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