2024년 3월 8일 알고리즘 문제풀이
문제
난이도
Lv.1
코드
1
2
3
4
5
6
7
8
9
10
11
12
def solution(participant, completion):
arr = {}
for runner in completion:
if runner not in arr:
arr[runner] = 1
else:
arr[runner] += 1
for player in participant:
if arr.get(player):
arr[player] -= 1
else:
return player
n-1개의 참가자 목록을 길이가 n인 리스트에서 탐색할 때 최악의 경우 n*(n-1), O(n**2)의 수행시간이 걸린다. 길이가 n인 리스트에서 1개를 탐색할 때 최악의 경우 n만큼 반복해야 하기 때문. 하지만 dictionary에선 상수의 값이라 O(1)이 n번 소요된다. dictionary에서 in 연산자는 해당 key가 존재하는지 찾아주고 get은 value 값을 반환해준다.
