코딩테스트 연습 - 실패율

코딩테스트 연습 - 실패율

실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

# 오류코드

37.0 / 100.0 : 런타임 에러 및 시간초과
O(n)O(n)+O(n)O(n)*O(n) => O(n^3)

def solution(N, stages): 
    fail_percent = dict()
    failed = 0
    people_len = len(stages)
    for i in range(1, N+1): 
        for j in range(people_len):
            if stages[j] <= i:
                failed += 1               
        fail_percent[i] = failed/people_len
        people_len -= failed
        for k in range(failed):
            if i in stages:
                stages.remove(i)
        failed = 0

    new_dic = sorted(fail_percent.items(), key=lambda x:x[1], reverse=True)
    return list(dict(new_dic).keys())

70.4 / 100 : 런타임 에러
O(n)*O(n) => O(n^2)
count 시간복잡도 : O(n) -> 완전탐색

def solution(N, stages): 
    fail_percent = dict()
    users = len(stages)
    for i in range(1, N+1):
        count = stages.count(i)
        fail_percent[i] = count / users
        users -= count
    
    new_dic = sorted(fail_percent.items(), key=lambda x:x[1], reverse=True)
    
    return list(dict(new_dic).keys())

# 정답코드

못풀겠어서 질문하기 참고함ㅠㅠㅠ => 그 스테이지에 도전한 사람들의 수가 0이 되어버리는 경우를 예외처리
#예외처리가 제대로 안된 경우 테스트케이스에서 런타임 오류 발생 !!!

def solution(N, stages):  
    fail_percent = dict()
    users = len(stages)
    for i in range(1, N+1):
        if users == 0: # 도전자가 0이 되는 경우
            fail_percent[i] = 0
            continue        
        count = stages.count(i)
        fail_percent[i] = count / users
        users -= count

                
    
    new_dic = sorted(fail_percent.items(), key=lambda x:x[1], reverse=True)
    
    return list(dict(new_dic).keys())