문제
https://school.programmers.co.kr/learn/courses/30/lessons/42576?language=python3
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
입출력 예
participant completion return
["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"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.
※ 공지 - 2023년 01월 25일 테스트케이스가 추가되었습니다.
1) 리스트로 접근방법
잘못된 접근 : remove() 사용
def solution(participant, completion):
sp = sorted(participant)
sc = sorted(completion)
for s in sc:
sp.remove(s)
return sp[0]처음에는 위 방법대로 접근하여 풀어보았다.
이는 Time Out 이 발생하게 되었다.
왤까???
문제는 remove() 의 작동방식에 있었다.
list.remove(x)
Remove the first item from the list whose value is equal to x. It raises a ValueError if there is no such item.
https://docs.python.org/3/tutorial/datastructures.htmlx에 해당하는 원소인지를 하나씩 접근, 이에 대한 삭제처리를 한다. 따라서 시간복잡도는 O(N)이다.
참고로 Python 사용에 대한 시간복잡도를 확인하고자 한다면 아래 링크를 꼭 참고해보는 게 좋겠다.
https://wayhome25.github.io/python/2017/06/14/time-complexity/
그렇다면 어떻게 리팩토링하면 좋을까?
수정된 접근 : if문을 통한 없는 사람 찾기
def solution(participant, completion):
#1
sp = sorted(participant)
sc = sorted(completion)
#2
for idx,s in enumerate(sc):
if(sp[idx] != s):
return sp[idx]
#3
return sp[-1]- #1
- participant 와 completion 을 정렬한다.
- #2
- 정렬된 completion 기준으로 일치하지 않는 원소가 있다면 반환한다.
- #3
- 만약 끝에 일치하지 않는 선수가 있어 남아있는 선수가 있다면, 마지막 원소를 반환한다.
2) 해쉬로 접근방법
위 방법은 다음 idea에 기반한다.
A리스트 - B리스트 = 남은 인원
그렇다면 우리는 해시를 사용한 idea에 기반하여 접근할 수 있지 않을까?
각 원소에 해시를 부여하여 일치성을 판별하고, 남은 원소를 반환
이에 따라 다음과 같이 코드를 구현할 수 있을 것이다.
def solution(participant, completion):
#1
hashP = dict()
sum = 0
#2
for p in participant:
hashP[hash(p)] = p
sum += hash(p)
#3
for c in completion:
sum -= hash(c)
#4
return hashP[sum]- #1
- key:value 자료구조인 dictionary 를 정의한다.
- #2
- 각 participant 의 hash 값을 key 로 하여 저장한다.
- 이 때, 총 hash 값을 계산한다.
- #3
- participant의 총 hash 값에서 각 completion 의 hash 값을 뺀다. 이 때 남은 값은 completion 에 없는 participant의 hash 값이 된다.
- #4
- 남은 participant 의 hash 값에 대한 value 를 찾는다.
접근법 다시 되돌아보기
1) 리스트 접근 :: 정렬을 통해 각 선수들을 비교하며 확인할 수 있다.
- #1
- participant 와 completion 을 정렬한다.
#1 sp = sorted(participant) sc = sorted(completion) - #2
- 정렬된 completion 기준으로 일치하지 않는 원소가 있다면 반환한다.
#2 for idx,s in enumerate(sc): if(sp[idx] != s): return sp[idx] - #3
- 만약 끝에 일치하지 않는 선수가 있어 남아있는 선수가 있다면, 마지막 원소를 반환한다.
#3 return sp[-1]
def solution(participant, completion):
#1
sp = sorted(participant)
sc = sorted(completion)
#2
for idx,s in enumerate(sc):
if(sp[idx] != s):
return sp[idx]
#3
return sp[-1]2) 해시 접근 :: 각 선수의 해쉬값에 대한 비교를 통해 확인할 수 있다.
- #1
- key:value 자료구조인 dictionary 를 정의한다.
#1 hashP = dict() sum = 0 - #2
- 각 participant 의 hash 값을 key 로 하여 저장한다.
- 이 때, 총 hash 값을 계산한다.
#2 for p in participant: hashP[hash(p)] = p sum += hash(p) - #3
- participant의 총 hash 값에서 각 completion 의 hash 값을 뺀다. 이 때 남은 값은 completion 에 없는 participant의 hash 값이 된다.
#3 for c in completion: sum -= hash(c) - #4
- 남은 participant 의 hash 값에 대한 value 를 찾는다.
#4 return hashP[sum]
def solution(participant, completion):
#1
hashP = dict()
sum = 0
#2
for p in participant:
hashP[hash(p)] = p
sum += hash(p)
#3
for c in completion:
sum -= hash(c)
#4
return hashP[sum]