코딩테스트 - 완주하지 못한 선수 (프로그래머스)

코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다.
(지문 하단에 별도 저작권 표시 문제 제외)
코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다.

코딩테스트 정보

• 프로그래머스
• python
• level 1
• 점수 : 캡쳐 못함
• 문제 링크

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다.
단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

participant	completion	return
[“leo”, “kiki”, “eden”]	[“eden”, “kiki”]	“leo”
[“marina”, “josipa”, “nikola”, “vinko”, “filipa”]	[“josipa”, “filipa”, “marina”, “nikola”]	“vinko”
[“mislav”, “stanko”, “mislav”, “ana”]	[“stanko”, “ana”, “mislav”]	“mislav”

풀이 방식

■■■■ 문제 요약 ■■■■

두 리스트의 원소 중 한쪽에만 포함되어있고, 다른쪽엔 없는 원소 찾기
한쪽 혹은 양쪽에 어떤 원소는 2개 이상 포함될(동명이인) 수 있다.

■■■■ 접근 방식 ■■■■

두 리스트를 정렬시킨 후, 서로의 원소를 순차적으로 비교하여 일치하지 않는 원소를 찾아낸다.

풀이 코드

나의 풀이 코드

def solution(participant, completion):
  answer = ''
  
  # 두 리스트를 정렬시키고
  participant.sort()
  completion.sort()

  # 두 리스간 원소 비교
  for i in range(len(participant)):
    try:
      if participant[i] != completion[i]:
        answer = participant[i]
        break
    # completion[i] 가 없으면, participant[i]가 정답
    except:
      answer = participant[i]
  
  return answer

다른 풀이 1

collections 의 counter 메서드를 이용한다.
이 메서드는 리스트에 어떤 원소가 몇 개 포함되어있는지를 dict 형태로 반환한다.

import collections

def solution(p, c):
  p.sort()
  c.sort()
  result = collections.Counter(p) - collections.Counter(c)
  
  return list(result)[0]

p = [“mislav”, “stanko”, “mislav”, “ana”]
c = [“stanko”, “ana”, “mislav”]

• print(p)
  Counter({‘mislav’: 2, ‘ana’: 1, ‘stanko’: 1})

• print(c)
  Counter({‘ana’: 1, ‘mislav’: 1, ‘stanko’: 1})

• result
  Counter({‘mislav’: 1})

다른 풀이 2

특정 값에 대해 고유의 int 형 숫자를 반환하는 hash 메서드를 이용하는 방법.
여기에 처리 속도가 list형(O(1) ~ O(N)) 보다 빠른 dict형(O(1)) 을 함께 이용한다.

def solution(p, c):
  answer = ''
  temp = 0
  dic = {}
  for part in p:
    dic[hash(part)] = part
    temp += int(hash(part))
  for com in c:
    temp -= hash(com)
  answer = dic[temp]

  return answer

코드의 진행을 예시로 들어보자면.. 아래와 같다.

p = [“mislav”, “stanko”, “mislav”, “ana”]
c = [“stanko”, “ana”, “mislav”]

hash(“mislav”) = 100
hash(“stanko”) = -200
hash(“mislav”) = 100
hash(“ana) = 150

dic = {100:”mislav”, -200:”stanko”, 150:”ana”}

for 문을 통한 temp의 계산 결과 = 100 - 200 + 100 + 150 -(-200) - 150 - 100
temp = 100

answer = dic[temp(=100)] => ‘mislav’
너무도 매력적인 풀이이다.

리뷰

특정 Object에 고유의 키값을 부여할 때는 hash 메서드

처리속도는 dict 형이 list 형보다 빠를 수 있다. (느리지는 않다.)