[프로그래머스] 완주하지 못한 선수 파이썬

문제 :

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

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

 

 

풀이과정 :

 

해쉬 문제라는데 내가 해쉬가 뭔지 잘 모른다 . . . 

 

처음에는 list 로 만들어서 list 안에 같은 값이 있으면 remove 시켜주는걸 생각해서 만들었다 

 

def solution(participant, completion):
    for i in completion:
        participant.remove(i)

    answer = participant[0]
    return answer

 

그래서 나온 소스코드인데 테스트케이스는 합격이지만 효율성에서 0점을 맞았따 !! ^^... 왜그런가 했더니 

remove() 는 처음부터 탐색하는 아주 비효율적인 함수여서 비록 for문을 하나 썼지만 remove 로 인해서 O(n^2) 의 시간복잡도를 갖게되어 효율성 부분이 0점이 나온거다 즉 ! O(n) 정도로 만들어줘야한다는 슬픈 소식

 

그래서 이용한게 딕셔너리를 이용한 풀이다 

 

각 이름에 +1 씩 해주고 completion 에 있는 이름들은 -1 씩해주는 형태로 만들어주었따 

그리고 마지막엔 딕셔너리의 value 가 가장 큰 친구를 출력해줬다

 

def solution(participant,completion):
    new_dict = {}
    for i in participant:
        if i in new_dict:
            new_dict[i] += 1
        else:
            new_dict[i] =1
    
    for j in completion:
        new_dict[j] -=1

    answer = max(new_dict.keys(),key=(lambda k: new_dict[k]))
    return answer

그래서 나온 소스코드 "max 출력 부분이 특이했다 lambda 를 사용해야했음"

 

정답 !

 

그 밖의 풀이과정 

1. 간단한 풀이 

import collections


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

아마 딕셔너리 - 딕셔너리를 해주는 코드인것같다 collections 가 어떤건지 한번 찾아봐야겠다

 

2. 정석의 Hash 함수 풀이 

 

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

 아마 출제자가 의도한것과 가장 근접한 풀이가 아닐가 싶다 hash 함수가 뭔지 또 공부해야겠다

 

 

배운것,공부할것 :

1. lambda 의 활용

2. hash 함수 ? , hash ? 

3. collections.Counter() 찾아보기