내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
완주하지 못한 선수
ps:problems:programmers:42576
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 완주하지 못한 선수 ====== ===== 풀이 ===== * 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}}
ps/problems/programmers/42576.txt
· 마지막으로 수정됨: 2022/05/03 09:51 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로