프로그래머스 - 해시: 완주하지 못한 선수

문제 설명

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

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

제한사항

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

입출력 예

participantcompletionreturn

["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

 

시간 복잡도를 고려하지 않은 나의 풀이

def solution(participant, completion):
    answer = ''
    for i in completion:
        participant.remove(i)
    answer = answer.join(participant)
    return answer

설명

완주한 사람들을 for문으로 돌려 참가자들 리스트에서 제거해 주는 식으로 생각해봤다. for 문은 O(n) 그리고 remove라는 함수도 리스트를 모두 확인 후 맞는 값을 제거하는 방식으로 O(n)으로 총 시간 복잡도가 O(n**2)이 나온걸 볼 수 있다. 형편이 없다는 소리다. 다시 풀어보자.

 

정렬을 이용한 코드 O(n*log(n))

def solution(participant, completion):
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    return participant[-1]

설명

각 각의 명단을 정렬을 해주었다. 정렬을 해서 보면 단 한명만 차이가 나기 때문에 print를 찍어보면 다른 부분 하나를 볼 수 있다. 

한명이 더 적은 완주자 리스트의 길이를 기준으로 for문으로 돌고 인덱스에 따른(정렬된 리스트 비교) 각 이름들이 나오겠고 그 이름이 다른 부분이 완주하지 못한 참가자가 된다. (*완주를 했다면 완주자 리스트와 같겠지?? 정렬을 했으니까!) 

그래서 그 부분이 for문 안에 예외 처리이다! 

 만약, 위 조건에 걸리지 않는다면 참가자리스트와 완주자 리스트가 같다는 말! 결국 참가자 리스트 중 마지막 녀석이 완주하지 못한 사람이 되겠다!

 

느낀점

 쉬운 문제라고 생각했다. 다른 사람들의 풀이를 보면 collection.Counter를 사용하여 딕셔너리 형태의 객체를 만들어줘서 빼주는 것도 볼 수 있는데, 이 방법도 직관적이고 좋은 풀이 인 것 같다. 딕셔너리는 - 연산이 안되지만 collections의 Counter는 객체 형태를 반환하기 때문에 - 연산이 가능하다.

import collections


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

 

해시를 활용한 알고리즘 O(n)

def solution(participant, completion):
	d = {}
    for x in participant:
    	d[x] = d.get(x, 0) + 1
        
    for x in completion:
    	d[x] -= 1
        
    dnf = [k for k, v in d.items() if v > 0]
    answer = dnf[0]
    return answer

설명

해시는 파이썬의 딕셔너리 자료구조이다. key와 value를 지정하여 탐색을 하기에 시간복잡도를 상수로 접근할 수 있다.

1) 참가자의 이름으로 key 값을 설정해주고 d.get(x, 0) 해당하는 key값이 없다면 value를 0으로 반환해주고 아니면 1을 더해주는 식 동명이인의 경우 늘어날 수록 1이 더해진다.

 

2) 완주한 사람의 이름을 확인하고 1을 빼준다. 결국엔 완주하지 못한 사람은 1이고 나머지는 다 0값을 갖는다.

 

3) value가 0이 아닌 사람을 찾아서 반환한다. 결국 1명이니까 dnf라는 리스트 첫번째 값을 리턴해준다.

 

@딕셔너리와 관련된 함수들

**get(x) 함수는 x라는 Key에 대응되는 Value를 돌려준다. 앞에서 살펴보았듯이 a.get('name')은 a['name']을 사용했을 때와 동일한 결괏값을 돌려받는다.

다만 다음 예제에서 볼 수 있듯이 a['nokey']처럼 존재하지 않는 키(nokey)로 값을 가져오려고 할 경우 a['nokey']는 Key 오류를 발생시키고 a.get('nokey')는 None을 돌려준다는 차이가 있다. 어떤것을 사용할지는 여러분의 선택이다.

       *get(x, 0) 은 없다면 none이 아닌 0을 반환해라라는 의미

 

**items 함수는 Key와 Value의 쌍을 튜플로 묶은 값을 dict_items 객체로 돌려준다. dict_values 객체와 dict_items 객체 역시 dict_keys 객체와 마찬가지로 리스트를 사용하는 것과 동일하게 사용할 수 있다.