사용자 도구

사이트 도구


ps:problems:programmers:42576

완주하지 못한 선수

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호42576
문제명완주하지 못한 선수
레벨Level 1
분류

기초

시간복잡도O(n*l)
인풋사이즈n<=100,000, l<=20
해결날짜2021/03/27
태그

고득점 Kit - 해시

풀이

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

코드

코드 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 collections


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

코드 2

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

코드 3

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

코드 4

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

코드 5

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

코드 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
"""


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)

토론

댓글을 입력하세요:
F Z​ R A​ P
 
ps/problems/programmers/42576.txt · 마지막으로 수정됨: 2022/05/03 09:51 저자 teferi