Link : 프로그래머스 > 고득점 키트 > 완주하지 못한 선수
Language : Python3
평균 점수 : 보통
Keyward
💡 해시
Solution
particiapnt에는 있고,completion에는 없는 한 명을 찾는다.- 효율성에서 오답으로 체크될 수 있으므로, 어떻게 풀어야 가장 효과적일지 고민해야 한다.
나의 코드
⑴ sort/for loof 를 사용한 풀이
채점 : 1031(+7)
키워드는 해시였지만 일단 직관화하여 for문으로 풀어보았다.
정렬을 먼저 한 후, for문을 순회하며 두 배열을 비교하였다.
def solution(participant, completion):
answer = ''
# 1. 각 배열을 정렬
participant.sort()
completion.sort()
# 2. completion 길이 만큼 순회
for i in range(len(completion)):
# 3. participant 와 값을 비교하여 같지 않은 것을 출력
if participant[i] != completion[i]:
answer = participant[i]
return answer
# 4. 순회를 마쳤으나 값이 발견되지 않았을 경우, participant의 마지막 값을 출력
answer = participant[-1]
return answer테스트는 통과했지만,
sort의 시간복잡도 O(logN) + for문의 시간복잡도 O(N) = O(NlogN)의 시간 복잡도를 가진다.
최적화된 코드
⑴ hash를 사용한 풀이 ›› better
def solution(participant, completion):
answer = {}
# 1. 딕셔너리에 참가자 : 동명이인수로 저장
for p in participant:
answer[p] = answer.get(p, 0) + 1
# 2. completion 에 포함되는 key의 value를 -1 한다.
for c in completion:
answer[c] = answer[c] - 1
# 3. participant 에는 있지만 completion 에는 없는 이름만 value 가 1로 남게되니 그것을 리턴
for i in answer:
if answer[i] : return i인자로 주어진 participant의 길이가 n 일 때,
n에 비례하는 선형 시간 복잡도(linear time complexity) O(N)을 가진다.
⑵ Counter 클래스를 사용한 풀이 ›› better
import collections
def solution(participant, completion):
# 1. participant의 Counter를 구한다
# 2. completion의 Counter를 구한다
# 3. 둘의 차를 구하면 정답만 남아있는 counter를 반환한다
answer = collections.Counter(participant) - collections.Counter(completion)
# 4. counter의 key값을 반환한다
return list(answer.keys())[0]Note
1. HashTable (HashMap)
hash 란, 임의의 길이를 갖는 임이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다. 쉽게 말해서, 입력값을 아무거나 넣더라도, 각기 다른 출력값을 반환하는 것이다.
파이썬 문제에서 hash 가 키워드라면 별도의 hash table 을 구성할 필요 없이 dioctionary 자료형을 사용하면 된다.
key와value쌍으로 이루어진 데이터 구조. (ex.딕셔너리)key를 이용하여value을 찾는다.- 메모리는 많이 사용하지만, 저장된 데이터를 순차적으로 찾는게 아니므로 속도가 빠르다는 장점이 있다.
- 연산의 (평균)시간복잡도가 O(1)으로, 매우 빠르게 값을 찾아낼 수 있다.
- 검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용.
2. dict.get(key, default=None)
- 첫번째 인자 : 찾고자 하는 키
- 두번째 인자 : 찾고자 하는 키가 없으면, 두 번째 인자를 반환한다.
dictionary를 사용하다 보면, 정의된 딕셔너리에서 찾고자 하는 key의 value를 가져오고 싶을 때가 있다. 그런데 혹시 내가 찾고자 하는 key가 정의된 딕셔너리에 없는 경우도 있을 것이다. 이럴 때 dict.get(key, default=None) 함수를 사용하면 key값이 없어도 오류를 발생 시키지 않고 None을 반환시킨다.
dict = { 'a': 2022, 'b': 2023 }
result = dict.get('a','Nothing')
print(result) # 20223. Counter 클래스
collections모듈을 이용한다.- 파이썬의 기본 자료구조인 사전(dictionary)를 확장하고 있기 때문에, 사전에서 제공하는 API를 그대로 다 시용할 수가 있다.
list나set을 인자로 넘기면 각 항목을 키로 해서 개수를 알려준다.return타입은dictionary이다.
from collections import Counter
list = ['Hello', 'HI', 'How', 'When', 'Where', 'Hello']
print(Counter(list))...
...
Counter({'Hello': 2, 'HI': 1, 'How': 1, 'When': 1, 'Where': 1})