[프로그래머스 / Python] 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

실패한 풀이

def solution(participant, completion):
	participant.sort()
    completion.sort()
    for i in range(len(completion)):
    	name = participant[i]
        if name == completion[0]:
        	completion.remove(name)
        else:
            return name
    return participant[-1]

아무래도 remove() 함수 사용 때문에 효율성이 좋지 않은 것 같다. remove()의 시간 복잡도는 O(N)이라고 한다. 삭제할 원소를 찾는 데 걸리는 시간이다.

나의 풀이 : Sort,Loop

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for part, comp in zip(participant, completion):
        if part != comp:
            return part
    return participant[-1]

사실 계속 효율성 부분에서 시간 초과로 실패해서 다른 사람의 풀이를 참고했다.

zip() 함수를 사용해서 비교하고, 값이 다르면 바로 return한다.

다른 사람의 풀이 : Counter

import collections


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

collections 모듈의 Counter를 사용한 풀이다.
list로 Counter 객체를 생성하면, list의 각 원소가 key값, 각 원소의 개수가 value값인 dictionary 자료형의 객체가 생성된다.
아래 예시를 보면 이해가 쉽다.

import collections

ex_list = ['a', 'b', 'c', 'c']
ex_counter = collections.Counter(ex_list)
print(ex_counter)

>>> Counter({'a': 1, 'b': 1, 'c': 2})

그리고 Counter 객체 간에는 뺄셈 연산이 가능하다.
collections.Counter(participant) - collections.Counter(completion) 연산을 통해 completion에는 없는 하나의 key값을 찾는다.

다른 사람의 풀이 : Hash 이용

def solution(participant, completion):
	hashDict = {}
    sumHash = 0
    
    for part in participant:
    	hashDict[hash(part)] = part
    	sumHash += hash(part)
        
    for comp in completion:
    	sumHash -= hash(comp)
       
    return hashDict[sumHash]

우선 해시 테이블 hashDict를 만든다.
이때, 해시테이블은 Key와 Value의 쌍으로 데이터를 저장하는 자료구조이다. Python의 dictionary는 HashTable로 구현되어 있기 때문에 {}로 hashDict를 생성한다.

HashTable에 대해 추가적으로 설명하자면, Python의 List처럼 데이터를 순차적으로 찾지 않고 Key값을 통해 Value값을 찾기 때문에 연산의 평균 시간복잡도가 O(1)로 매우 빠르다.

다시 문제로 돌아와서, 해시테이블 hashDict에 participant의 값을 모두 추가한다.
이때, hash(part) 를 통해 참가자 이름(part)의 해시 값을 계산하고 이를 hashDict에 저장한다.
해시테이블의 Key는 각 참가자 이름(part)의 해시 값이 되고, Value은 참가자 이름(part)이 된다.

그리고 sumHash에 각 해시값을 더한다. 이후 해시값을 이용해 participant에는 있지만 completion에는 없는 참가자를 찾기 위함이다.

for문으로 completion의 값을 순회하면서 sumHash에서 각 hash(comp)들을 빼준다.
그럼 sumHash의 값은 participant에만 있는 참가자 이름(part)의 해시값이 되므로 해시 테이블 hashDict에서 Key값이 sumHash인 Value를 리턴하면 된다.

아래 예시를 보자.

participant와 completion이 다음과 같을 때

participant = ['park', 'kim', 'lee']
completion = ['kim', 'lee']

각 참가자 이름의 해시값인 Key값과 참가자 이름인 Value는 다음과 같을 수 있다.

Key	Value
3	park
16	kim
8	lee

그럼 sumHash = 3 + 16 + 8 = 27 이 되고, completion을 순회하는 과정에서 sumHash = 27 - 16 - 8 = 3 이 된다.
따라서 hashDict[3] == 'park'이기 때문에 이를 return 하는 것이다.

다음 글을 참고했다. https://mgyo.tistory.com/177