문제
https://programmers.co.kr/learn/courses/30/lessons/42576?language=python3
문제설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 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" |
자바스크립트 풀이
우선 자바스크립트 문법이 익숙하니 자바스크립트로 먼저 풀어보았다. 자바스크립트로는 생각보다 쉽게 풀 수 있었다.
function solution(participant, completion) {
participant.sort();
completion.sort();
for(var i=0; i < participant.length; i++){
if(participant[i] !== completion[i]){
return participant[i];
}
}
}
- sort()로 정렬하기
(만약 숫자를 비교하기위해서는 sort에 콜백함수 전달해줘야)함.오름차순:.sort((a,b) => a - b)) - !== 를 이용한 비교.
만약, 리스트를 돌면서 participant의 마지막 인덱스 전까지 completion과 값이 같다면 participants의 마지막 인덱스가 반환된다. participant의 마지막 인덱스에 해당하는 completion값은 undefined이므로 !== (데이터타입까지 비교)를 통한 대소비교가 가능하다.
파이썬 풀이
파이썬을 배우고 있는 단계이므로 문법이 아직 약하다.
파이썬에도 !==와 같은 대소비교가 있는 줄 알았는데 파이썬에는 !=밖에 없었다. 그래서 자바스크립트처럼 풀었더니 에러가 발생하였다.
그래서 !=를 통한 대소비교를 하고 마지막 인덱스 전 까지 다 같다면 마지막 인덱스가 다른 값이므로 리턴한다.
def solution(participant, completion):
participant.sort()
completion.sort()
for i in range(len(completion)):
if participant[i] != completion[i]:
return participant[i]
# 전부 다돌아도 없을 경우에는 마지막 주자 리턴
return participant[len(participant) - 1]
Hash를 이용한 Solution
participant배열을 가지고 Hash맵을 만든다. 선수의 이름을 Hash로 변환 후 Hash값을 key로 하고 선수 이름을 value로 하는 Dictionary를 만든다.
participant를 hash로 만든 key값을 다 더한다.
completion 배열을 돌면서 해당하는 hash값을 participant key의 총합에서 뺀다.
남은 값이 완주하지 못한 선수의 hash값이 된다.
def solution(participant, completion):
hashDict = {}
sumHash = 0
# participant list의 hash를 구하고 hash값을 더한다.
for part in participant:
hashDict[hash(part)] = part
sumHash += hash(part)
# completion list의 hash를 빼준다
for comp in completion:
sumHash -= hash(comp)
# 남은 값이 완주하진 못한 선수의 hash값이 된다.
return hashDict[sumHash]
print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))- hash()함수 이용
- hashDict에 key-value 형태로 해쉬값 담기
- Dictionary에서 hash값을 이용해 쉽게 search 할 수 있음
Counter solution
파이썬에서는 collection이라는 모듈안에 Counter라는 Built-in Class가 있는데 이 클래스는 리스트를 딕셔너리로 변환해서 각각의 요소가 몇개 있는지 셀 수 있다.
from collections import Counter
def solution(participant, completion):
answer = Counter(participant) - Counter(completion)
return list(answer.keys())[0]
print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))- participant의 Counter를 구한다.
- completion의 Counter를 구한다.
- 둘의 차를 구하면 남는 요소의 이름이 key로 오고 개수가 value로 남는다.
Counter{{'leo': 1}} Counter{{'leo': 1}}.keys() => dic_keys(['leo'])- 딕셔너리를 다시 list로 변환
list(dic_keys(['leo'])) => ['leo']
