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

🔗 문제 링크

---

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

프로그래머스

문제 설명
▶ 마라톤에 참여한 선수들 중 완주하지 못한 선수의 이름을 반환하도록 solution 함수를 작성해라.

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

 

✨ 풀이 과정

---

💡처음 생각해냈던 풀이 방법
1. participant 배열과 completion 배열을 선언한다.
2. 각각의 배열을 정렬한다.
3. 반복문을 이용하여 participant[i] != completion[i]인 경우 → 여러 명의 동명이인이 있는 경우에 동명이인들 중 한 명이 다 완주하지 못했을 경우에 해당되므로 동명이인을 반환해준다.
4. participant[i] = completion[i] 인 경우 → 동명이인이 없는 경우 제일 마지막에 있는 참가자가 완주하지 못한 참가자가 되는 경우에 해당되므로 제일 마지막에 있는 참가자를 반환해준다.

 

⬇️1차 시도 전체 코드

participant = ["kiki", "kiki", "eden"]
completion = ["eden", "kiki"]

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for part in range(len(completion)):
        # 여러 명의 동명이인이 있는 경우에 동명이인이 다 완주하지 못했을 경우에 해당된다.
        if participant[part] != completion[part]:
            return participant[part]
    # 동명이인이 없는 경우 제일 마지막에 있는 참가자가 완주하지 못한 참가자가 된다.
    return participant[-1]

print(solution(participant, completion))

→  하지만 이 풀이는 해쉬를 이용하는 방법이 아닌 정렬을 이용하는 방법이므로 해쉬를 이용해서 풀어보기로 하였다.

 

💡해시를 이용한 풀이 방법
1. Hash Map을 만든다.
· Hash Map: Key-Value 의 쌍을 관리하는 클래스이다.
· 여기서 Key는 hash한 값이고, Value 는 각 선수의 이름으로 설정한다.
2. Hash Map에 Participant를 추가한다.
· ‘Hashing한다’ 라고도 표현한다.
· 각 이름의 Hash값(Key)을 구하고 이 값들의 합을 구한다. → sumHash로 정의한다.
3. sumHash에서 완주한 선수의 Hash값을 뺀다.
· sumHash에서 완주자들의 Hash값을 빼면 완주하지 못한 사람의 Hash값만 남는다.
4. 남은 Hash값을 이용해서 Value를 찾으면 완주하지 못한 선수가 나오게 된다.

 

👩‍💻 최종 코드

---

def solution(participant, completion):
    #파이썬에서 dict 자료형이 해쉬 맵 역할을 수행하므로 별도의 라이브러리를 임포트하지 않아도 됌.
    #hashDict와 sumHash를 초기화한다.
    hashDict = {} 
    sumHash = 0
    
    for part in participant:
        # 1. Participant의 dictionary를 만든다.
        hashDict[hash(part)] = part
        # 2. Participant의 sum(hash)를 구한다.
        sumHash += hash(part)
    
    # 3. completion의 sum(hash)를 뺀다.
    for comp in completion:
        sumHash -= hash(comp)
    
    # 4. 남은 값이 완주하지 못한 선수의 hash 값이 된다.

    return hashDict[sumHash]