Programmers | 해시 - 완주하지 못한 선수 (Lv. 1)

[문제 설명]

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

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

 

[제한 사항]

- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.

- completion의 길이는 participant의 길이보다 1 작습니다.

- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

- 참가자 중에는 동명이인이 있을 수 있습니다.

 

[출처 : 프로그래머스]

 

문제에 대한 나의 접근

 

- 두 개의 배열정보(참여자, 완주자)를 받아 두 배열간 비교를 통해 해서 진행하면 될 것 이라고 생각했다.

- 처음엔, 심플하게 차집합으로 진행하면 되겠다라고 생각....

 

def solution(participant, completion):
    answer = list(set(participant) - set(completion)) # 참여자와 완주자에 대한 단순 차집합 연산
    
    if answer != []:
        return answer[0]
    else:    	
        return 0

 

그런데...

 

p = ['mislav', 'stanko', 'mislav', 'ana']
c = ['stanko', 'ana', 'mislav']

answer = solution1(p, c)
answer # 0

 

위와 같이 동명이인이 있는 경우 미완주자에 대한 이름이 반환되지 않았다...

그래서 단순 차집합 연산이 아닌 다시 방법을 생각해보기로 했다.

 

Python 내장모듈인 collections의 Counter 클래스를 사용하는 것으로 생각했다.

 

Counter는 '해시 가능한 객체를 세는 데 사용하는 딕셔너리 서브 클래스'로써

배열의 항목이 딕셔너리 key로, 항목의 개수를 딕셔너리 value로 저장이 된다. 

 

Counter 클래스 정보

 

from collections import Counter

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

 

p1 = ['leo', 'kiki', 'eden']
c1 = ['eden', 'kiki']

p2 = ['marina', 'josipa', 'nikola', 'vinko', 'filipa']
c2 = ['marina', 'josipa', 'nikola', 'filipa']

p3 = ['mislav', 'stanko', 'mislav', 'ana']
c3 = ['stanko', 'ana', 'mislav']

answer1 = solution(p1, c1)
answer1 # leo

answer2 = solution(p2, c2)
answer2 # vinko

answer3 = solution(p3, c3)
answer3 # mislav

 

이렇게 Counter 클래스를 사용해서 진행하니까 문제에서 요구한 답을 구할 수 있었다.

 

정답 제출 후  다른 풀이 방법을 사용해 풀이한 다른 분들의 결과물 들을 봤는데... 역시 많은 방법이 있었다.

그 중 문제 출제의도를 잘 파악해서 풀이한 내용을 한 번 봤다.

 

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

 

이 방법은 참여자 배열을 for 반복문으로 item을 하나씩 꺼내면서 꺼내지는 item의 해시값을 딕셔너리의 key로

참여자를 value로 저장한다. 그리고 item에 해당하는 해시값을 temp 변수에 저장을 한다.

 

완주자 배열은 for 반복문으로 item을 꺼내면서 꺼내지는 item의 해시값을 기존 참여자의 해시값들이 저장되어 있는

변수 temp와 비교해 있으면 빼는 작업을 진행한다.

 

변수 temp는 참여자의 해시값 정보가 있는 변수에서 완주자의 해시값을 뺀 나머지인 미완주자의 해시값만 남는다.

미완주자의 해시값을 딕셔너리에 key로 입력해 해당 해시값에 대응되는 value인 미완주자의 이름 정보를 결과로

반환한다.

 

문제 영역이 해시이다 보니 위 방법이 해당 값들의 해시 정보를 이용해서 푸는 방법이 어떻게 보면 문제 출제 의도를

잘 파악하고 풀이한 방법이 아닐까하는 생각이 든다.