문제

프로그래머스 실패율

원래 코드

def solution(N, stages):
    
    stage_dict = dict()
    # 500
    for i in range(1,N+1):
        stage_dict[i] = {"success":0,"stay":0}
    

    # 200000
    master_users = 0
    for stage in stages:
        if stage != N+1:
            stage_dict[stage]["stay"] += 1
        else:
            master_users += 1
        # 500 <- 여기서 시간 초과
        for success_stage in range(1,stage):
            stage_dict[success_stage]["success"] += 1
        
    answer = []
    # 500
    for stage_status in stage_dict.keys():
        stay = stage_dict[stage_status]["stay"]
        success = stage_dict[stage_status]["success"]
        if success == 0 and stay == 0:
            failure_percentage = 0
        else:
            failure_percentage = stay / (stay + success)
        answer.append([1-failure_percentage, stage_status])
    
    # 500
    answer.sort()
    
    # 불필요한 함수가 시간을 잡아먹는다!
    print(stage_dict)
    print(answer)
    
    answer = [x[1] for x in answer]
    
    return answer

문제점

테스트 케이스 22번에서 문제가 발생했다.
stages의 길이가 200000, 그리고 그 원소의 대부분이 500인 경우에 시간 초과가 발생했다.
그리고 시간 초과가 나는 부분의 코드는 위의 주석으로 표시해놨다.

해결한 코드

def solution(N, stages):
    # 22번 테스트 케이스
    
    stage_dict = dict()
    # 500
    for i in range(1,N+1):
        stage_dict[i] = {"success":0,"stay":0}
    

    # 200000
    master_users = 0
    for stage in stages:
        if stage != N+1:
            stage_dict[stage]["stay"] += 1
        else:
            master_users += 1
            
    # sigma 500
    for stay_stage in range(1,N+1):
        if stage_dict[stay_stage]["stay"] != 0:
            for success_stage in range(1,stay_stage):
                success_users = stage_dict[stay_stage]["stay"]
                stage_dict[success_stage]["success"] += success_users
    
    # sigma 500
    for _ in range(master_users):
        for success_stage in range(1,N+1):
            stage_dict[success_stage]["success"] += 1
        
    
    answer = []
    # 500
    for stage_status in stage_dict.keys():
        stay = stage_dict[stage_status]["stay"]
        success = stage_dict[stage_status]["success"]
        if success == 0 and stay == 0:
            failure_percentage = 0
        else:
            failure_percentage = stay / (stay + success)
        answer.append([1-failure_percentage, stage_status])
    
    # 500
    answer.sort()
    
    # 불필요한 함수가 시간을 잡아먹는다!
    print(stage_dict)
    print(answer)
    
    answer = [x[1] for x in answer]
    
    return answer

해결 방법

반복문이 중첩되는 경우, 내부 반복문의 로직을 밖으로 끄집어내서 중첩을 없앤다.