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

https://programmers.co.kr/learn/courses/30/lessons/42576?language=python3

 

첫 번째 시도 

def solution(participant, completions):

    for i in reversed(range(len(participant))):
    
        num_of_completions = completions.count(participant[i])
        if num_of_completions != 0:
            
            completions.remove(participant[i])
            del participant[i]
            
               
            
    return participant[0]

참가자 명단과 완주자 명단을 비교해가며 완주자 명단에 존재할 시 삭제해나가는 코드

 

효율성 0점..

Python에서는 remove 메소드가 최악의 경우 O(n) 이 되어버려서 그다지 효율적이지 못한 코드라고 한다. 

 

def solution(participant, completions):
    answer=[];
    
    for i in reversed(range(len(participant))):
    
        num_of_completions = completions.count(participant[i])
        if num_of_completions!=participant.count(participant[i]):
            answer.append(participant[i])
            break;
    
            
            
               
    
    return answer[0]

하나 하나 제거해나가는 방식을 버려야했다. 생각해보니 count로 끝내버리면 될거같았다. 결과는 ...

 

ㅋㅋ

생각해보니 count도 시간복잡도 O(n)을 잡아먹는다..  

 

def solution(participant, completions): 
    answer=[];                         
    participant = sorted(participant)
    completions = sorted(completions)
    for idx in range(len(participant)):
        if idx+1 == len(participant):break;
        elif participant[0:idx] + participant[idx+1:len(participant)] == completions:
            
            answer.append(participant[idx])
    
    return answer[0]

 

slicing을 통해 해결해보려했지만 이번엔 sorted가 O(nlog(n))을 잡아먹는단다.. ㅋㅋ

 

def solution(participant, completions): # participant = ['leo','muslav','kiki'] 
    answer=dict();                          # completions = ['leo','kiki']
    for participant in participant:
        answer[participant] = answer.get(participant,0)+1
    for completion in completions:
        if answer[completion]>0:
            answer[completion] -= 1
        if answer[completion]==0:
            del answer[completion]

    
    return list(answer.keys())[0]

결국 질문하기 글들을 봤는데 Hashing으로 풀면 편하다해서 구현(거의 copy)한 코드.. 

팀장님이 자기는 시간복잡도 고려해야할때 먼저 쓰는게 Hash 함수라고 하셨는데 진짜 흘려들었다가 시간 많이 날렸네

Hash는 key-value를 mapping해주는 방식을 말하는거같다.. 공부하기!!