[프로그래머스] 해시 - 완주하지 못한 선수 (파이썬)

혼자 정보보안 공부를 시작하면서 여러가지를 책으로도 공부하고 인터넷으로도 공부하고 했지만 제일 오랜 시간을 투자하지 못했던 것이 자료구조, 알고리즘 공부이다. 오늘부터 최소 이틀에 한문제라도 풀어보려 한다.

 

해시는 키-값 (key-value) 쌍으로 데이터를 저장하는 자료구조로 프로그래머스(programmers)에서는 해당 자료구조를 학습하기 위한 4가지 문제를 제공하고 있다.

 

 

프로그래머스 해시 - 완주하지 못한 선수, 문제확인

문제 설명은 아래와 같다.

 

---

단 한명의 선수를 제외하고는 모든 선수가 마라톤을 완주함

선수들의 이름이 담긴 배열 participant이 주어짐

완주한 선수들의 이름이 담긴 배열 completion이 주어짐

완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성

마라톤 경기에 참여한 선수의 수는 1명 이상, 100000명 이하

completion 길이는 participant 길이보다 1 작음 (=단 한명의 선수만 완주하지 못함)

동명이인이 있을 수 있음

 

 

다음은 입출력 예이다.

 

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

 

 

프로그래머스 해시 - 완주하지 못한 선수, 문제풀이 (파이썬)

계속 participant를 돌며 completion에 일치하는 사람이 있으면 제외하는 방식보다는 애초에 처음에 sort를 해주었다. sort를 해주었으니 같은 인덱스의 participant 값과 completion의 값이 일치하지 않는다면 그 사람이 완주하지 못한 사람이 된다.

 

따라서 일치하지 않는 경우 v를 리턴해주고 그외(마지막까지 인덱스가 간 경우)는 마지막 값 (participant[-1])을 리턴해준다.

 

#어차피 완주못한 사람은 1명이기 때문에
#처음에 sort를 해주면 반복문을 여러번 돌지 않아도 됨

def solution(participant, completion):
    
    participant.sort() #participant=participant.sort()가 아님! 주의
    completion.sort()
    for i,v in enumerate(participant):
        if i==len(participant)-1:
            return participant[-1]

        #sort했으니까 일치하지 않는다면 그사람이 완주못한 사람    
        if v != completion[i]:
            return v

 

 

그럼 다음과 같이 테스트 케이스들을 통과할 수 있다.

 

 

 

아마도 프로그래머스에서 제일 쉬운 문제가 아닐까 예상해본다. 자료구조와 알고리즘은 정말 쥐약이기 때문에 앞으로 힘든 여정이 예상된다...

 

 

 

다른 사람의 풀이 확인 - 파이썬 collections 모듈

collections 모듈을 이용한 초간단한 풀이가 있는데 collections.Counter는 각 요소의 개수를 딕셔너리 형태로 반환해준다. 예를들어 아래와 같은 test 리스트가 있을 때 collections.Counter에 넘겨주면 {'aa': 2, 'cc': 1,..} 과 같은 형태가 반환이 되는 것이다. 

 

test = ['aa', 'cc', 'dd', 'aa', 'bb', 'ee']
print(collections.Counter(test))

# Counter({'aa': 2, 'cc': 1, 'dd': 1, 'bb': 1, 'ee': 1})

 

따라서 collections.Counter(participant)에서 collections.Counter(completion)을 빼주면 완주하지 못한 선수만 남게 되는 것이다. 따라서 인덱스가 0만 있을테니 반환 값은 answer.keys()를 리스트 형태로 변환한 것에 [0] 값이 된다. 애초에 딕셔너리에서 빼기가 가능한 것도 처음 알았다. ㄷㄷ

 

import collections

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