Programmers - 완주하지 못한 선수
오늘은 프로그래머스에 있는 완주하지 못한 선수 문제를 풀어 보았다. 어디 내놓기 부끄러운 코딩 실력이지만 공부하는 과정이니 하나씩 블로그에 올려보고자 한다. 앞으로 알고리즘 공부 관련 포스트는 내가 푼 (틀린 혹은 가끔 맞은) 풀이를 서술하고 정답 풀이를 아래에 올릴 예정.
문제의 링크는 여기를 클릭하면 된다.
1. 문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
1-1. 제한사항 🚨
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
2. 나의 풀이 🤔
def solution(participant, completion):
part = sorted(participant)
comp = sorted(completion)
for i in range(0, len(comp)):
if comp[i] == part[i]:
continue
else:
return part[i]
return part[len(part)-1]정렬을 활용해 풀었다. 알파벳 순으로 정렬해 같은 index에 원소가 다르다면 완주하지 못한 선수임을 알 수 있었다. 중복이 있는 경우도 해결이 가능하다. 이렇게 풀 경우 O(NlogN)의 시간복잡도를 가진다.
효율성 테스트도 통과하기는 했지만 더 좋은 풀이가 있는지 찾아보았다.
3. 다른 풀이
[해시] - 완주하지 못한 선수
def solution(participant, completion):
d = {}
for x in participant:
d[x] = d.get(x, 0) + 1
for x in completion:
d[x] -= 1
not_finish = [k for k, v in d.items() if v > 0]
answer = not_finish[0]
return answer
get()
여기서 get(x) method는 Key에 대응되는 Value를 돌려준다. 따라서 여기서 사용된 get(x, 0)은 x가 있으면 Value를 return하고 없으면 0을 돌려주는 것.
즉, 여기서 참여한 사람들 모두에 대해 Value를 1로 부여하게 되고 동명이인이 있을 경우 Value += 1 되어 해당 이름을 가진 사람의 수 가 Value가 된다.
ex) ["mislav", "stanko", "mislav", "ana"]
여기서 Dictionary를 생성하게 된다면
{'mislav':2, 'stanko':1, 'ana':1} 과 같이 생성됨을 알 수 있다.
items()
위의 get() 함수가 Value를 얻는 것이라면, items()는 key와 value를 둘 다 출력한다.
아무튼
위와 같이 해시를 사용해 풀이를 하는 것이 정석이라고 한다.
