완주하지 못한 선수 - 알고리즘 공부

간만에 알고리즘 공부를 하였다. 내용은 프로그래머스 홈페이지(programmers.co.kr)에 있는 해쉬 level1에 있는 문제이다

 

문제내용은 아래와 같다

 

출처 : 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/42576?language=python3

처음에는 그냥 반복문으로 완주한 선수들 명단을 하나씩 빼다가 참가자명단에서 하나씩 빼면 되는줄 알았다..

그러면 될 줄 알았다....

 

근데 이게 무슨일이람?

정확성 테스트에는 다 통과했으나 효율성테스트에서 빵점을 받았다

 

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. 한 시간밖에 안걸려서 다행이다.