[Python] 프로그래머스 | 실패율

요즘 파이썬으로 알고리즘 문제를 풀고 있다.

파이썬 다운 코드 보다는.. 스스로 생각한 로직으로 솔루션을 제시하는 것에 집중하고 있다.

 

코드에 주석이 섞여있는데  요구사항을 읽으며 주석을 간단히 달아두는 게 도움이 많이 된다.

동료들과 우테코 최종 테스트 대비 스터디를 하며 아직은 주석을 달아가며 구현하는게 필요하다고 느꼈다.

아직 내가 작성한 코드를 한 눈에 알아보는 능력이 부족하기도 하고,

요구사항을 분석하며 필요한 로직을 주석으로 달아 구현해 나가면 좀 더 세세하게 설계를 고민할 수 있는 것 같다.

 

def solution(N, stages):
    answer = [] # 실패율이 높은 스테이지 내림차순
    
    # 실패율 = 스테이지 도달&아직 클리어x 플레이어 수 / 스테이지 도달한 플레이어 수
    
    # N : 전체 스테이지 개수
    # stages : 사용자가 현재 멈춰있는 스테이지 번호, N+1은 마지막스테이지 클리어한 사용자
    
    # stages 돌면서 실패율 계산
    fail_dic = dict()
    max_stage = N + 1
    for i in range(1, max_stage):
        total_player = 0
        yet_player = 0
        for stage in stages:
            if stage >= i:
                total_player += 1
                if stage == i:
                    yet_player += 1
        if total_player == 0:
            fail_dic[i] = 0
        else:
            fail_dic[i] = yet_player / total_player
            
    # 내림차순으로 정렬
        # 실패율이 같으면 작은 번호의 스테이지가 먼저온다
        # 스테이지에 도달한 유저가 없으면 실패율 0으로 정의
    sorted_lst = sorted(fail_dic.items(), key= lambda item:item[1], reverse=True)
    
    answer = list(item[0] for item in sorted_lst)
        
    return answer

 

문제를 풀면서 두 가지 문제점이 있었다.

 

런타임 오류

채점을 하면 몇몇 테스트에서 런타임 오류가 발생했는데,

이는 스테이지에 도달한 플레이어(total_player)가 없는 경우 0으로 정의하지 않아

스테이지에 도달했으나 클리어하지 못한 플레이어 수 / 스테이지에 도달한 총 플레이어 수

위 계산식이 0 / 0 이 되어 오류가 발생한 것이다.

 

아래는 오류가 발생한 코드이다.

# stages 돌면서 실패율 계산
    fail_dic = dict()
    for i in range(1, N+1):
        total_player = 0
        yet_player = 0
        for stage in stages:
            if stage >= i:
                total_player += 1
                if stage == i:
                    yet_player += 1
        fail_dic[i] = yet_player / total_player # <-여기서 런타임 오류 발생!

 

문제를 해결하기 위해 간단히 else 문을 추가해 계산식에 도달하기 전,

스테이지에 도달한 플레이어(total_player)가 0인 경우 실패율을 0으로 정의하도록 수정했다.

        if total_player == 0:
            fail_dic[i] = 0
        else:
            fail_dic[i] = yet_player / total_player

 

시간 복잡도

지금까지 알고리즘 문제를 풀면서 시간 복잡도를 크게 고려하지 않았다.

하지만 이번 문제의 실행 속도를 보니 이제는 시간복잡도를 다시 공부하고, 설계 시 꼭 고려해야겠다고 느꼈다.

테스트 돌다 터지는 줄 알았다..

 

내 코드에서 스테이지에 도달한 플레이어(total_player)를 구하기 위해 for문을 돌며 일일히 계산하고 있다.

Collections.counter(len(stages)) 를 사용했다면 O(N*M) -> O(M)으로 줄일 수 있다.

• M: stages의 길이. (사용자의 수)

이후 사용자 수를 구해 다음 루프를 돌기 전, 사용자의 수 - 스테이지에 도달했지만 클리어하지 못한 사용자의 수 를 계산하면, 다음 스테이지에 도달한 사용자의 수를 구할 수 있다.

 

앞으로는 자료구조와 시간 복잡도에 대해 공부해 적용하는 것을 목표로 해야겠다 :)