1. 완주하지 못한 선수

문제 설명

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

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

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

• completion의 길이는 participant의 길이보다 1 작습니다.

• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

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

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

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

2. 문제 접근

• Participant: N명의 참가자, Completion: N-1명의 완주자들

• 비교해서 없는 것 하나만 찾으면 된다.

• 해결책

  1. 정렬한 뒤, 반복문을 통해 1대1 비교하여 서로 다른 항목이 나온 사람을 반환
  2. 해시 이용
  3. collections.Counter 이용

해결책 1번

1. Participant, Completion 정렬

2. 반복문 돌며 index의 값 다른 Participant 찾기
   1) Completion 배열 기준으로 반복

3. 반복문 다 돌아도 나오지 않으면 Participant 마지막 값
   1) 정렬된 상태이기 때문에 가능
   2) participant[-1]

def solution(participant, completion):
    answer = ''

    # 정렬
    participant.sort()
    completion.sort()

    # 완주자 길이만큼 참가자를 찾아서 없는 사람을 찾는다
    for i in range(len(completion)):
        if(participant[i] != completion[i]):
            return participant[i]

    # 완주자 길이만큼 다 돌아도 없는 경우는 마지막 참가자가 완주하지 못한 선수이다
    return participant[len(participant)-1]

    return answer

해결책 2번

1. HashMap 만들기
   1) Key-Value의 Pair를 관리하는 클래스
   2) Key는 hash한 값, Value는 각 선수의 이름

2. HashMap에 Participant 추가
   1) 각 이름의 hash 값을 구하고, 이 값들의 합을 구함

3. sumHash에서 완주한 선수의 Hash값 빼기
   1) sumHah에서 완주자들을 제외시키면, 남는 1명이 정답

4. 남은 Key로 Value 찾기
   1) hashDict[sumHash]

def solution(participant, completion):
    hashDict = {}
    sumHash = 0

    # 참가자의 directory 만들기, [해시 Key] = 해시 value
    # 참가자 해시 Key 들의 합
    for part in participant:
        hashDict[hash(part)] = part
        sumHash += hash(part)

    # 참가자 해시 Key 들의 합 - 완주자 해시 Key = 완주 못한 참가자의 Key
    for comp in completion:
        sumHash -= hash(comp)

    # 남은 참가자 해시 key-value 값이 완주하지 못한 선수
    return hashDict[sumHash]

해결책 3번

1. participant Counter로 변환하기
   1) Python이 제공하는 collections 라는 모듈의 한 class이다.
   2) list를 가지고 Counter를 생성하면, Counter는 Key가 이름이고, Value가 count 인 dictionary를 반환하게 된다.
   

2. completion 배열을 Counter로 변환하기
   

3. participant와 completion 배열 간의 차 구하기
   1) collections.Counter(participant) - collction.Counter(completion)
   2) Counter class는 상호간의 뺄셈 연산을 지원한다.
   => 뺄셈 연산 한번으로 둘 participant는 있고, completion에는 없는 사람을 찾을 수 있다.
   

4. 마지막 Counter에서 Key값을 읽어오기
   1) 단계의 결과는 dictionary 로 나오는데, 이 중 우리는 Key를 꺼내와야 한다.
   2) list(answer.keys())[0]
   3) Keys를 list로 형변환 하고, 이 중 0번 째 인덱스의 값을 읽어온다
   => 위 동작을 수행하고 나면 {"A" : 1} 이라는 Dict로부터 ["A"] 라는 list를 꺼내오게 되고, 여기서 [0] 으로 접근하면

import collections
def solution(participant, completion):

    answer = collections.Counter(participant) - collections.Counter(completion)

    return list(answer.keys())[0]