완주하지 못한 선수

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

"""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]

"""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)

"""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)

"""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)

"""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)

"""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)