문제 링크

이 문제는 해시에 분류되어 있는 문제로, 리스트 두 개를 받아서 하나의 다른 리스트에 없는 문자열을 출력하는 문제다.

쉬워보여서 적당히 리스트 비교하면서 값을 출력했더니 통과하길래 제출했더니 정확성 점수는 만점인데, 효율성 점수가 0였다.

리스트 remove 함수를 써서 만들었더니 복잡도가 높게 나타난 모양이었다. = 리스트의 삽입/삭제는 O(N)이다.

그래서 다른 방식으로 풀이하고자 했는데 내가 생각한 아이디어는 먼저 각각의 리스트를 정렬하고 index를 비교해보면서 값이 다르면 그 값을 추출하는 것이었다.

나의 풀이

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(completion)]

풀이를 하고 나니 해시에 분류되어있는데 해시를 안 쓴 것 같아서 다른 풀이를 찾아봤다.

다른 사람 풀이

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

이 풀이는 Counter를 사용하여 풀이했는데, 굉장히 간결하다. Counter로 생성된 객체끼리 뺄셈이 가능해서 차집합을 구해서 키를 반환하면 정답이 나온다.

다른 사람 풀이 2

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x, 0) + 1
    for x in completion:
        d[x] -= 1
    not_finish = [k for k, v in d.items() if v > 0]
    answer = not_finish[0]
    return answer

이 풀이는 get()을 사용해서 participant에 value를 부여하는데, 인자로 x,0을 넣어주어 x가 있으면 x 값을 리턴하고 그렇지 않으면 0을 반환한다고 한다.

그래서 dictionary d에 데이터를 저장해주면 중첩된 인물도 카운트되어 2가 되니 구별할 수 있다.

다음으로 completion 리스트를 순회하면서 dictionary를 순회하며 -1을 더해준다. 그러면 결과적으로 완주하지 못한 사람은 1 이상이 되며 이를 판별하여 반환하면 끝이다.