[programmers] lv.1 완주하지 못한 선수

문제 설명 문제 바로가기

제한 사항

입출력 예

풀이 접근

• 처음에는 participant list에서 각 원소를 받아 해당 원소가 completion에 존재 하지 않는다면 해당 i를 return, i를 포함하고 있는 수가 participant와 completion에서 다르다면 또다시 i를 return하도록 설정
• 그러나 100,000의 길이 제한에서 for문 내의 count()함수는 시간 복잡도 함수가 n^2 꼴에 가까워지면서 시간 초과가 발생하였다.
• sort()를 이용해서 두 함수가 달라지는 순간의 i값을 return시켰고, 그렇지 않다면 가장 마지막 값을 return하였다. (시간 복잡도 T(n) = O(n)으로 그침 )

나의 풀이

#1

#시간초과
def solution(participant, completion):
    answer = ''
    for i in participant:
        if i not in completion:
            return i
        else:
            if participant.count(i) > completion.count(i):
              return i

#2

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(participant)-1):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

다른 사람의 풀이

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

• collections의 Counter 잘 사용하면 유용한 것 같다. Counter끼리의 뺄셈 가능
• 예시
  출력 결과의 type 잘 봐두기!