해당 문제는 프로그래머스 고득점 kit 해시에 속하는 문제로, key-value쌍으로 데이터를 찾는 것이 풀이의 핵심이다. 파이썬에서는 dictionary를 활용하여 해시 문제를 해결한다.
해시(Hash) 알고리즘에 대한 설명은 이 포스팅 참고 !
문제
문제 설명
정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
내 풀이
import collections
def solution(participant, completion):
par_dict = collections.Counter(participant)
for com in completion:
if com in par_dict:
par_dict[com] = par_dict[com] - 1
for key, value in par_dict.items():
if value == 1:
return key-
해당 문제의 경우 동명이인이 존재할 수 있다는 전제가 있기 때문에, 무작정 participant를 dictionary 형태로 변환하면 동명이인을 반영할 수 없다. (dictonary는 key값의 중복 X)
-
따라서 collection 모듈의 Counter 함수를 활용하여 데이터를 개수로 빠르게 변환하였다.
-
participant 리스트안에 있는 값들을 Counter 함수를 활용해 dictionary 형태로 변환하고, for문으로 completion 리스트를 훑으면서 해당 값이 dictionary에 존재할 경우 해당 value값을 하나씩 빼주었다.
-
결과값은 key, value값을 dictionary의 item 함수를 활용해 value가 1인 값에 대해서만 해당 key값을 반환하도록 하였다.
다른 사람의 풀이1
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]-
collection 모듈의 Counter 함수는 덧셈 뺄셈이 가능하다.
-
Counter 함수를 활용해 dictionary를 만들면 자동으로 큰 값부터 정렬되기 때문에, 결과값은 answer이라는 dictionary의 가장 맨 앞에 위치하는 key값을 출력하도록 하였다.
다른 사람의 풀이2
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-
python에 내장된 hash 함수를 활용한 풀이
-
hash 함수는 객체에 할당되는 해시값을 반환해준다. 즉, 고유값을 반환해주는 것
-
part = com이면 해당 해시값인 hash(part) = hash(com)이므로, 마지막으로 남는 temp 값에 대한 value를 반환하면 결과값으로 part, participant 리스트에 있는 참가자명이 반환될 것이다.
해당 포스팅을 작성하는데 참고한 블로그
