문제
[완주하지 못한 선수]
수 많은 마라톤 선수들이 마라톤에 참여
단 한명의 선수 제외하고는 모든 선수가 마라톤 완주
마라톤 참여 선수 이름 배열 participant
완주한 선수들 이름 배열 completion
완주하지 못한 선수의 이름을 return하라
<제한>
마라톤 경기 참여 선수 1명 이상 100000명 이하
completion 길이 = participant 길이 - 1
참가자 이름은 1개 이상 20 이하 알파멧 소문자
동명이인 존재 가능 → participant에는 joy가 4번, completion에는 3번 있다면 joy가 완주하지 못한 선수일 것이다. 선수의 이름들이 몇 번씩 등장했는지 알아야 한다. → hash와 밀접한 부분
•
마라톤 참여 선수 수에 따라 프로그램의 크기가 결정될 것
•
O(log n) 정도의 복잡도가 나오면 좋을 것이다
자료구조 및 알고리즘 선택
이름이 아닌 번호가 주어졌다면 선형배열(linear array)를 사용할 수 있을 것이다. 최대 100,000의 길이를 갖는 linear array에 선수 번호들을 저장할 수 있을 것.
그러나 이름이 주어졌기 때문에 가능한 모든 이름의 조합을 찾으려면 26(알파벳 수)^20 x 100,000만큼의 크기가 필요
문자열로 접근할 수 있는 자료구조가 무엇이 있을까?
hash
index 대신 key로 매핑된 값을 찾을 수 있음
이렇게 leo와 eden이 같은 hash bucket을 가리키게 되면 충돌이 발생했다고 하고, bucket을 그림과 같이 옆으로 늘리는 식의 방식으로 해결할 수 있다.
[풀이 예시]
participant = ['a', 'b', 'a', 'c']
completion = ['a', 'b', 'c']
python dictionary 구조 활용 : 내부적으로 hash를 사용해 O(1)시간에 접근이 가능
{'a' : 2, 'b' : 1, 'c' : 1} → completion에 있는 수만큼 빼줌 → {'a' : 1, 'b' : 0, 'c' : 0}
⇒ a가 완주하지 못했다
풀이 코드
<hash 사용 (dictionary 자료구조 사용) >
def solution(participant, completion):
d = {}
for p in participant:
d[p] = d.get(p, 0) + 1
for c in completion:
d[c] -= 1
for k, v in d.items():
if v == 1:
return k
Python
복사
dictionary의 get() 메소드
dictionary의 items()메소드
결국 d.items()부터 반복문까지 participant의 길이에 비례해 시간이 늘어나기 떄문에 linear time algorithm O(N)의 복잡도 → hash table을 통해 값을 불러오도록 해 O(1)로 값을 불러와서 가능
<collections 모듈의 Counter객체 활용>
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]
Python
복사
collections 모듈 : dict, list, set및 tuple에 대한 대안을 제공하는 특수 컨테이너 데이터형을 구현
그 중 class Counter 는 해시 가능한 객체를 세는 데 사용하는 dictionary subclass이다. 요소가 dictionary의 key가 되고 개수가 dictionary값으로 저장된다.
! 대신 Counter 객체는 없는 key값을 호출할 경우 keyError대신 0을 반환
! dictionary 의 삽입된 순서를 기억하는 기능을 상속
c = Counter(['eggs', 'ham'])
c['bacon'] # 0을 반환
c = Counter(['b', 'a', 'a', 'f', 'c'])
# c = {'b':1, 'a':2, 'f':1, 'c':1}
Python
복사
<정렬 방법 사용>
participant와 completion을 정렬(.sort() 메소드) 해서
두 리스트를 값을 앞에서부터 비교하다보면 둘이 달라지는 부분의 선수가 완주하지 못한 선수일 것.
반복문이 끝날 때 까지 둘이 같으면 정렬된 participant 마지막 원소가 완주하지 못한 선수일 것
def solution(participant, completion):
participant.sort()
completion.sort()
for i in range(len(completion)):
if participant[i] != completion[i]:
return participant[i]
return participant[len(participant)-1]
Python
복사
이 경우에는 sort()메소드 자체가 O(NlogN)의 복잡도를 가지기 때문에 해쉬방법보다 복잡도가 높습니다.
