====== 완주하지 못한 선수 ======

===== 풀이 =====
  * BOJ의 [[ps:problems:boj:10546]]과 완전히 동일한 문제이다.
  * 기본적으로는 사람마다 등장 횟수를 세어서, participant쪽의 등장 횟수가 completion쪽의 등장 횟수보다 많은 사람을 찾으면 되는 매우 간단한 문제이다. python에서는 collection.Counter을 쓰면 구현도 매우 간단하고 ([[#코드 1]]), 마음만 먹으면 이 방식으로 1줄에도 짤 수 있다. 속도도 O(n*l)으로 최적이다.
  * 다만 이것 외에도 이 문제를 풀수 있는 재미있는 아이디어들이 있다.
    * counter에 participant와 completions을 모두 합친다음에, 카운트가 홀수인 사람을 찾는다 ([[#코드 2]])
    * participant와 completion을 소팅하고, 앞에서부터 비교하다가 달라지는 지점을 찾는다. 그 지점의 partcipant가 완주하지 못한 선수이다. ([[#코드 3]])
    * partcipant에 있는 사람 이름의 해쉬값의 합에서, completion에 있는 사람 이름의 해쉬값의 합을 뺀다. 그러면 완주하지 못한 선수의 해쉬값만 남는다. 이 해쉬값에 해당하는 사람 이름을 리턴하면 된다 ([[#코드 4]])
    * 두 그룹의 해쉬값의 합을 각각 구해서 빼는 대신, 두 그룹의 해쉬값을 모두 xor해도 완주하지 못한 선수의 해쉬값만 남는다. ([[#코드 5]])
    * 해쉬값을 갖고 계산하는 대신, 각 자리의 글자마다 아스키값을 갖고서도 똑같은 방식을 쓸 수 있다. ([[#코드 6]])


===== 코드 =====
==== 코드 1 ====
<dkpr py>
"""Solution code for "Programmers 42576. 완주하지 못한 선수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42576
- Solution link: http://www.teferi.net/ps/problems/programmers/42576
"""

import collections


def solution(participant, completion):
    partcipants_counter = collections.Counter(participant)
    completion_counter = collections.Counter(completion)
    return list(partcipants_counter - completion_counter)[0]
</dkpr>

==== 코드 2 ====
<dkpr py>
"""Solution code for "Programmers 42576. 완주하지 못한 선수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42576
- Solution link: http://www.teferi.net/ps/problems/programmers/42576
"""

import collections


def solution(participant, completion):
    counter = collections.Counter(participant) + collections.Counter(completion)
    return next(x for x, count in counter.items() if count % 2 == 1)
</dkpr>

==== 코드 3 ====
<dkpr py>
"""Solution code for "Programmers 42576. 완주하지 못한 선수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42576
- Solution link: http://www.teferi.net/ps/problems/programmers/42576
"""

import itertools


def solution(participant, completion):
    participant.sort()
    completion.sort()
    return next(p for p, c in itertools.zip_longest(participant, completion)
                if p != c)
</dkpr>             


==== 코드 4 ====
<dkpr py> 
"""Solution code for "Programmers 42576. 완주하지 못한 선수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42576
- Solution link: http://www.teferi.net/ps/problems/programmers/42576
"""


def solution(participant, completion):
    h = sum(hash(x) for x in participant) - sum(hash(x) for x in completion)
    return next(x for x in participant if hash(x) == h)
</dkpr> 

    
==== 코드 5 ====
<dkpr py>         
"""Solution code for "Programmers 42576. 완주하지 못한 선수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42576
- Solution link: http://www.teferi.net/ps/problems/programmers/42576
"""

import functools
import operator


def solution(participant, completion):
    h = functools.reduce(operator.xor,
                         (hash(x) for x in participant + completion))
    return next(x for x in participant if hash(x) == h)
</dkpr>

==== 코드 6 ====
<dkpr py>     
"""Solution code for "Programmers 42576. 완주하지 못한 선수".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42576
- Solution link: http://www.teferi.net/ps/problems/programmers/42576
"""


def solution(participant, completion):
    s = [0] * 20
    for name in participant + completion:
        for i, c in enumerate(name):
            s[i] ^= ord(c)
    return ''.join(chr(x) for x in s if x)
</dkpr>        
            
{{tag>프로그래머스 ps:problems:programmers:Level_1}}