[Python/프로그래머스] 42576. 완주하지 못한 선수

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

해시

https://school.programmers.co.kr/learn/courses/30/lessons/42576

 

 

입력 : 참가자 리스트, 성공자 리스트

출력 : 실패한 사람 이름 문자열

 

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차 풀이

# 1차 풀이 (정확성 성공, 효율성 실패)
def solution(participant, completion):
    for name in completion:
        participant.remove(name)
    return participant[0]

# 그냥 remove 메서드로 다 빼버릴까?
# -> 이렇게 푸니 시간초과 나옴...
# => O(n^2) 라서 그렇다.

# 입력 : 마라톤 선수들의 이름이 담긴 리스트 participant와,
# 완주한 선수들의 이름이 담긴 배열 completion
# 출력 : 완주하지 못한 선수 이름 문자열

# 입력은 20 * 100,000 = 200만까지 가능, 시간 제한 1초 가정 하 여유로움.
# => 아님. 저 20은 그냥 참가자 이름이라 시간 복잡도 계산엔 영향 x.
# 시간 제한이 1초가 아닌듯.

2차 풀이

# 2차 풀이 (정확성 실패, 효율성 실패)
def solution(participant, completion):
    for name in participant:
        if name not in completion:
            return name
            
# 동명이인이 있을 경우 null을 반환해버림.
# 얘도 결국 O(n)임...
# => 아님. O(n^2)임.

1차, 2차 풀이 둘다 O(completion*participant) 라서

사실상 O(n^2)이 돼버린다!!!!

⇒ O(n) 풀이를 떠올려야 할 듯 하다.

⇒ 해보니, 둘다 각각 Counter()로 Counter 객체에 추가하면 O(n) + O(n) = O(n) 이라서 할만해 보이는데?

 

찾아보니, 딕셔너리는 덧셈, 뺄셈, 교집합, 합집함을 지원하지 않아 직접 구현해야 해서 복잡한데, Counter 객체는 `덧셈, 뺄셈, 교집합, 합집합`을 지원한다!!

https://wikidocs.net/233689

Counter 객체의 뺄셈은 약간 차집합처럼 작동하는데, C1 - C2 시 C1에 있는 key들에서, C2와 겹치는 key들의 value를 뺀 것이 결과가 되고, value가 0인 놈은 C1에서 제거됨.

⇒ 그냥 바로 두 Counter 객체 간 뺄셈 진행하면 쉽게 풀리겠는데??

⇒ 뺄셈 연산도 대략 `O(n)`정도 걸릴 것임.

3차 풀이

# 3차 풀이(정답, 정확성 통과, 효율성 통과)
from collections import Counter
def solution(participant, completion):
    counter_1 = Counter(participant) # O(n)
    counter_2 = Counter(completion) # O(n)
    # ex. Counter({'leo': 1}) 객체
    counter_result = counter_1 - counter_2 # O(n)
    
    result = list(counter_result.keys())[0]
    
    return result

교훈) 시간복잡도를 줄이고 싶으면, 중첩(nested)이 아닌 병렬로 단위연산을 구성하면 된다!!

O(n^2) → O(n) + O(n) = O(n)

정답 확인함

from collections import Counter


def solution(participant, completion):
    counter = Counter(participant)

    for name in completion:
        counter[name] -= 1

    for name, counts in counter.items():
        if counts == 1:
            return name

이렇게 풀면 굳이 Counter 객체간의 뺄셈을 떠올릴 필요가 없으니, 더 쉽게 떠올릴 수 있어 보인다.

---

250217 재풀이

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