완주하지 못한 선수 - 알고리즘 공부
간만에 알고리즘 공부를 하였다. 내용은 프로그래머스 홈페이지(programmers.co.kr)에 있는 해쉬 level1에 있는 문제이다
문제내용은 아래와 같다

처음에는 그냥 반복문으로 완주한 선수들 명단을 하나씩 빼다가 참가자명단에서 하나씩 빼면 되는줄 알았다..
그러면 될 줄 알았다....
근데 이게 무슨일이람?
정확성 테스트에는 다 통과했으나 효율성테스트에서 빵점을 받았다
import copy
def solution(participant, completion):
answer = ''
copyParticipant = copy.deepcopy(participant)
for player in completion:
copyParticipant.remove(player)
answer = copyParticipant.pop()
return answer
내가 처음 작성한 코드 나름 깊은복사도 썼다 ㅋ

왜 그런가 찬찬히 보니 사실 딱 봤을 때 저 코드의 시간 복잡도는 O(n)처럼 보이지만 실제로는 O(n^2)이다.
무슨말이냐? for문에서 리스트에서 remove하는 부분이 보이는가?
for player in completion:
copyParticipant.remove(player)
즉 이 remove의 시간복잡도도 O(n)이다. 결국 위 코드는 따지고 보면 for문을 두번 돌리는 것과 같다는 뜻이다
(이와 관련해서 각 자료형의 메소드의 시간복잡도도 확인해 보면 좋을거같다
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt)
어 쨋 든
이래저래 방법을 찾다가 우연히 파이썬의 Collections자료를 보게 되었는데
(https://docs.python.org/3/library/collections.html#collections.Counter)
이 라이브러리는 무려 집합의 개념을 쉽게 사용해 줄 수 있게 해준다. 즉 차집합도 가능하다는 이야기
그렇다면 참가자명단-완주자명단의 차집합을 구한다면 자료가 단 하나만 남게 되지 않을까? 라는 아이디어를 가지게 되었고 바로 코드로 쓱싹 만들어 보았다.
from collections import Counter
def solution(participant, completion):
answer = ''
a=Counter(participant)
b=Counter(completion)
c=a-b
temp=list(c.keys())
answer=temp.pop()
return answer
변수명이 맘에 안들더라도 그냥 넘어가주세용~
Counter()메소드의 매개변수로 리스트를 넣어주면 딕셔너리형태의 자료형으로 넘겨준다.
그리고 두가지를 - 해주면 차집합처럼 알아서 계산을 해주고 여기서 마지막 남은 자료하나만 쓱 가져오면 된다.
결과는?

위와 같이 잘 되었다.
결론
1. 시간복잡도.. 잘 체크하자
2. 라이브러리를 잘 쓰면 편하다
3. 한 시간밖에 안걸려서 다행이다.