알고리즘 풀이: [프로그래머스] 완주하지 못한 선수

https://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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

---

문제 풀이

선수 이름을 key로 하고 등장 횟수를 value로 하는 해시(파이썬에서는 딕셔너리)를 생성합니다. participant에 대해서는 value를 증가시키고, completion에 대해서는 value를 감소시킵니다. 최종적으로 등장 횟수(value)가 1인 선수가 완주하지 못한 선수입니다.

 

해시 테이블을 자세히 살펴봅니다.

해시 테이블 구성 예시

participant에 있는 선수들은 모두 등장 횟수를 증가시켜줍니다. 특히 mislav 선수는 2번 등장했으므로 등장 횟수가 2가 됩니다.

 

completion에 있는 선수들은 모두 등장 횟수를 감소시켜줍니다. 문제 정의상 participant와 completion은 하나 차이밖에 나지 않습니다. 즉 완주하지 못한 한 명의 선수의 등장 횟수는 1이 될 것입니다. 

 

따라서 최종 해시 테이블에서 value가 1인 선수를 찾으면 문제를 해결할 수 있습니다.

 

소스 코드

메인 솔루션 함수

def solution(participant, completion):
    table = {p: 0 for p in set(participant)}

    # 등장횟수 + 1
    for p in participant:
        table[p] += 1
    # 등장횟수 - 1
    for p in completion:
        table[p] -= 1

    for k, v in table.items():
        if v == 1:
            return k


if __name__ == '__main__':
    assert solution(["leo", "kiki", "eden"], ["eden", "kiki"]) == "leo"
    assert solution(["marina", "josipa", "nikola", "vinko", "filipa"], 
                    ["josipa", "filipa", "marina", "nikola"]) == "vinko"
    assert solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]) == "mislav"

 

프로그래머스 문제 해결

github 주소: https://github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%201/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%20%EB%AA%BB%ED%95%9C%20%EC%84%A0%EC%88%98.py

dhsong95/-PRACTICE-Programmers-Algorithm