DDOING

Record my study

완주하지 못한 선수

내 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def solution(participant, completion):
    part = {}
    for p in participant :
        if p in part.keys():
            part[p] += 1
        else:
            part[p] = 1
    for c in completion:
        if part[c] != 0:
            part[c] -= 1
    for key,value in part.items():
        if value == 1:
            answer = key
            
    return answer
  • part : dict 타입
    • key = 참여한 사람
    • value = 같은 이름의 사람 수

participant 리스트에서 key,value 를 받아와 저장한다

completion 리스트에서 iter 를 돌며 같은 이름이 있는 key 의 value 를 -1 한다

그 후 part 에 만약 value 가 1이 남아있다면 answer 에 string 타입으로 저장한다

정답

1
2
3
4
5
6

import collections


def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

회고

밑의 코드는 내가 처음 실행했을 때의 코드로, 효율성 테스트에서 5개 테스트 전부 다 시간초과가 나왔다.

1
2
3
4
5
6
7

def solution(participant, completion):
    answer = ''
    for a in completion:
        if a in participant:
            participant.remove(a)
    answer = participant[0]
    return answer

원인으로 생각한 코드는

1
2
3

for a in completion:
        if a in participant:
            participant.remove(a)

여기에서 시간 복잡도가 많이 올라갔을 것이라고 판단하여 iter 를 돌며 list 내에 string 을 제거하는 방법보다는 dict 타입에서 value 를 count 하는것이 더 빠를 것이라고 판단했다

참고