[Python] 프로그래머스 알고리즘 해시- 완주하지 못한 선수

효율성을 생각하게 된 계기...

 

알고리즘 문제는 그냥 풀기만 하면 될 줄 알았는데 효율성도 생각해야한다는 것을 깨달았다. ..

이번 문제는 풀기는 간단하게 풀었지만 문제를 제출하자 효율성에서 통과하지 못했고 

문제를 틀렸다고 간주하였다... 

이걸 해결하는 과정에서 효율성에 대해 생각해볼 수 있었다. 

 

 

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. . 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant 와 완주한 선수들의 이름이 담긴 배열 completion 이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

 

첫번째 코드

def solution(participant, completion):
    answer=[]
    for i in participant:
        if i not in completion:
            answer.append(i)
        else:
            
            completion.remove(i)
            
    return answer[0]

 

 

사실 내가 생각했던 건, 어차피 선수들은 무조건 참가해야하므로 participant 에는 무조건 있을테고... 그렇다면 participant 에는 있는데 completion 에 없는 선수를 찾으면 되는 것 아닌가??? 라고만 생각했다. . . 

(갈길이멀다..)

 

 

따라서 정말 간단하게 리스트로 만들었더니 코드가 작동은 하여 결과값을 만들어내기는 하지만, 효율성이 떨어진다는 결과를 받았다. 

 

🤔 효율성이 떨어진다는 건 어떤 지적일까?

간단하게 말하면 ...코드를 실행할 때 시간이 너무 오래걸린다는 것이다. 오마이갓~ 

 

 

😇 다시 한번 생각을 해보도록 하자. . 

일단 해시 문제이고 어쨌든 두 배열을 비교하는 것은 확실하다.

휴..최대한 열심히 생각해보려 했는데 효율성 문제는 처음 봐서... 구글링을 해보았다. 

구글링과 다른 검색을 해본 결과 Counter라는 게 있다는 걸 알 수 있었다. 

 

📌 Counter

Collections 모듈의 Counter 객체는  컨테이너안의 데이터를 편리하고 빠르게 개수를 세도록 지원하는 계수기 도구이다. 

• Counter는 dict의 서브클래스이기 때문에 key 와 value 형태로 저장된다.
• 여기서 key는 요소이고, value는 요소의 갯수

즉 Counter(['a','a','b','b','b']) 이렇게 있다고 쳐보자

key	value
A	2
B	3

 

이런 식으로 요소의 갯수를 세주게 된다. 

 

따라서 우리도 각 요소의갯수를 세어서 요소가 없는 애를 반환하면 된다. 그리고 얘는 dict 형태처럼 저장하는데 우리는 '어떤 선수'인지만을 궁금한 것이기 때문에 value 값만 가져오면 된다. 

따라서 리스트 형태로 만들어주고, 리스트 에서 하나만 가져오면 된다. 

 

Counter를 이용한 두번째 시도

from collections import Counter

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

 

 

 

 

참고:https://docs.python.org/ko/3/library/collections.html