[프로그래머스/스터디 0주차] 해시 완주하지 못한 선수 Lv.1 - 파이썬(Python)/ Counter, Hash

(2021.08.03)

 

📑 문제

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

프로그래머스

문제 설명

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

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

제한사항

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

 

입출력 예

participant                                                               completion                                                                             return

["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

 

 

 

 

 

 

✒️ 풀이

 처음 풀이는 정말 별로였다.

 '음....그냥 completion 배열에 있는 객체들을 participant 배열에서 지우고 남은 하나를 주면 되는 것 아닌가?'

 맞다. 하지만 그렇게 하면 답은 나오지만 효율성에서 다 탈락하는 참사가 일어나고 만다.

def solution(participant, completion):
    answer = ''
    for i in range(len(completion)):
        if participant.count(completion[i]) >0:
            participant.remove(completion[i])

    return participant[0]

 

 한 마디로 위 코드는 효율이 빵점인 코드인 것이다!

 그렇다면 어떡하느냐. 나는 딕셔너리도 미숙하고...다른 메소드들도 잘 모른다.

 방법은 구글링 뿐!ㅠ.ㅠ

 세상엔 천재들이 많다. 다양한 방법들이 쏟아져 나왔다.

 그 중 프로그래머스에 개제된 방법은 바로

 

 

 

 Counter

 collections라는 라이브러리에 존재하는 함수이다. 

 결과를 딕셔너리로 리턴해준다.

 덧셈, 뺄셈 연산도 가능하다는 것이 무척이나 중요하다.

 뺄셈의 경우 -1이나 그 이하의 숫자가 나와도 0으로 리턴해주며, 0이 나오면 사라지는 것 같다.

 

 <정답 코드>

import collections

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

 

 

 

 위 코드를 보고 궁금해서 몇 개 찍어본 코드가 있다.."andrew"를 participant에 추가했다.

participant = ["mislav", "stanko", "mislav", "ana", "andrew"]
completion = ["stanko", "ana", "mislav"]

def solution(participant, completion):
    tmp = Counter(participant)-Counter(completion)
    
    print(tmp)
    #1 결과: Counter({'mislav':1, 'andrew':1})
    
    print(tmp['mislav'])
    #2 결과: 1
    
    print(tmp.keys())
    #3 결과: dict_keys(['mislav', 'andrew'])
    
    print(list(tmp))
    #4 결과: ['mislav', 'andrew']
    
    print(list(tmp).sort())
    #5 결과: None
    
    print(sorted(list(tmp)))
    #6 결과: ['andrew', 'mislav']

 

 Counter는 딕셔너리 형태로 리턴된다. 그러므로 여기서 딕셔너리의 keys() 혹은 values() 함수를 사용할 수 있다.

 딕셔너리는 안에서는 인덱스 접근이 안되기 때문에, list로 변환해주어야 값에 접근할 수 있다.

 이때 이유는 모르겠는데 5번은 결과가 안나오고 6번은 제대로 나온다. 흠...

 알파벳 순서로 보고 싶다면 Counter로 딕셔너리 형태를 만들기 전에 배열을 sort()하거나, 아니면 리스트로 변환 후에 sorted(list())를 하는 방법을 취할 수 있겠다.

 

 

 

 

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()함수는 들어온 값에 대한 고유값을 리턴해준다고 한다.

 즉 들어온 값(value)에 대한 고유값(key) 쌍이 지어지는, 일종의 딕셔너리 형태가 만들어질 수 있는 것이다.

 딕셔너리에 참여자들의 해시 값(고유 값: Key)와 이름 값(Value)을 모두 넣으며, 해시값의 합을 구한다.

 그리고 완주자들의 해시값을 참여자들의 해시값 합에서 뺀다.

 단 한 명만이 완주하지 못했다고 했으므로, 완주자들을 모두 빼고 나면 temp에는 완주하지 못한 단 한 명의 해시값만이 남게 된다.

 그 해시값을 통해 만들어두었던 딕셔너리에서 Value 값(이름)에 접근한다.

 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨