[programmers lv.1 python] 완주하지 못한 선수 풀이 (with 시간초과 해결)

문제

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

프로그래머스

코딩테스트 공부를 다시 시작했당

쉬운 문제지만 해결해 나갔던 과정을 기억해두고 싶어서 포스팅한다

문제 자체는 쉽다! 참가자 목록이랑 완주자 목록이 주어지는데 완주 못한 단 한 사람을 찾으면 됨

 

1차 코드 ➡️ 시간초과 실패

def solution(participant, completion):
    for c in completion:
        if c in participant:
            participant.remove(c)
    return participant[0]

 

1. 참가자 명단에 c (완주자)가 있으면 참가자 명단에서 해당 c를 제거한다.

2. 중복된 이름이 있어도, 한 번만 제거된다. (그래서 문제없이 통과될 거라고 생각했다)

ㅎ 효율성 테스트에서 다 시간초과로 실패가 떠버렸다.

participant.remove(c)는 리스트에서 해당 원소를 찾고 지우기 때문에, 입력이 크면 클 수록 기하급수적으로 느려진다. 

for문으로 순회하는 방식 말고 다른 방법을 찾아야겠다고 생각했다.

 

2차 코드 ➡️ 성공 (Counter 사용)

from collections import Counter

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

 

💡Counter 클래스
Counter는 파이썬의 collections 모듈에 포함된 특수한 딕셔너리 타입으로,
입력된 리스트에서 각 원소가 몇 번씩 나오는지 세어주는 자료구조이다.
사용 예시)

Counter(['jin', 'lee', 'jin'])
# 결과: Counter({'jin': 2, 'lee': 1})​

 

두 Counter의 차이 연산

각 리스트를 카운터에 넣고 차이를 구하면, 중복이 있더라도 완주 못 한 사람을 쉽게 구할 수 있다.

(참고: 일반 딕셔너리는 값을 빼지 못한다. Counter는 객체이기 때문에 값 빼기가 가능)

Counter(participant) - Counter(completion)

# Counter({'jin': 2, 'lee': 1}) - Counter({'jin': 1, 'lee': 1})
# 결과: Counter({'jin': 1})  <-- 즉 jin이 1명 완주 못함

통과~

 

---

두 방식 시간복잡도 비교

1. for문 + remove 방식

for c in completion:
    if c in participant:
        participant.remove(c)
return participant[0]

• for c in completion: 완주자 수 만큼(N-1) 반복
• if c in participant: participant에서 c를 검색
  • 리스트에서 원소를 찾으려면 O(N) (최악의 경우)
• participant.remove(c): 리스트에서 원소 삭제
  • 이 또한 O(N) (최악의 경우)
• 두 동작이 거의 한 번에 이뤄지므로, 각 반복마다 O(N)

총 시간복잡도 :
(N-1) * O(N) = O(N^2)

 

 

2. Counter 이용 방식

from collections import Counter

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

Counter(participant)

• 리스트를 한 번 순회해서 이름별로 세어야 함
• 리스트 길이가 N이라면 O(N)

Counter(completion)

• 위와 동일하게, 리스트 길이가 N-1이니 O(N)

Counter1 - Counter2 ( Counter(participant) - Counter(completion))

• 두 Counter를 비교하면서 각 key의 value를 뺌
• key 종류가 최대 N이므로 O(N)

list(answer.keys())[0]

• Counter에서 key 하나 꺼내는 작업(상수시간)
• O(1)

총 시간복잡도 :
O(N) + O(N) + O(N) + O(1) = O(N)

---

오늘자 요약

코테에서는 웬만하면 Counter 쓰자.