[Python] 실패율

programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

스테이지별 실패율을 구해서 스테이지를 실패율이 높은 순서대로 반환하는 문제입니다.

 

실패율은 문제에서 정의해 줬습니다.

• 실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

그리고 주의깊게 봐야 할 제한사항입니다.

• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

def solution(N, stages):
    dic = {}
    answer = []
    child = [0] * (N+1)
    parents = [len(stages)] * (N+1)

    for s in stages:
        if s == N+1:
            continue
        child[s] += 1

    for s in stages:
        for i in range(s+1, N+1):
            parents[i] -= 1

    for i in range(1, N+1):
        if parents[i] == 0:
            dic[i] = 0
            continue
        dic[i] = child[i] / parents[i]
        
    answer = sorted(dic, key=lambda x: dic[x], reverse=True)
    return answer

 

저는 실패율을 구하기 위한 분자와 분모를 구한 후 이들을 각각 계산시키는 방식으로 구현했습니다.

분자는 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수, 즉 현재 스테이지에 머물러있는 플레이어의 수 입니다.

단순히 stages 리스트를 검사하며 stages 넘버를 child 리스트의 인덱스 삼아 1씩 증가시켰습니다.

단, stages 리스트 내 값이 N+1일 경우는 모든 스테이지를 클리어한 경우임으로 행동을 취하지 않아야겠죠? (배열 인덱스 오류가 납니다)

 

분모를 구하기 위해서 사전에 parents 리스트를 플레이어의 수로 N+1만큼 초기화해줬어요.

현재 머물러있는 스테이지에 도달하기 위해서는 모든 이전 스테이지를 통과했어야겠죠?

이걸 조금만 달리 생각하면 현재 머물러있는 스테이지보다 높은 스테이지는 전부 통과하지 못했다는 뜻입니다.

그래서 분자를 구할 때 처럼 stages 리스트를 순회하되, 현재 스테이지를 초과한 스테이지는 모두 1씩 감소시켰습니다.

 

이제 실패율 계산을 위한 분자, 분모가 모두 준비되었습니다.

스테이지 당 실패율을 담아서 실패율을 기준으로 내림차순 정렬한 스테이지를 구하기 위해 딕셔너리를 사용할게요. 

 

또한, 위에서 언급한 제한사항을 지키기 위해서 '현재 스테이지에 도달한 사람들의 수'가 0일 때는 key = stage 넘버, value = 실패율을 담기 위한 딕셔너리 'dic'의 value를 0으로 설정해주고, 분모가 0일 때 발생하는 런타임 에러를 방지하기 위해 분자/분모를 계산하지 않고 다음 반복으로 넘어갑니다.

 

스테이지 당 실패율을 모두 구했다면, value를 기준으로 딕셔너리를 내림차순 해주면 답을 구할 수 있습니다.

 

다른 풀이

def solution(N, stages):
    answer = {}
    num = len(stages)

    for stage in range(1, N+1):
        if num != 0:
            count = stages.count(stage)
            answer[stage] = count/num
            num -= count
        else:
            answer[stage] = 0

    return sorted(answer, key=lambda x: answer[x], reverse=True)

 

딕셔너리를 사용하지 않고 list.count()로 stages 리스트 내 값의 개수(분자)를 구하고

num(분모)를 이용해 answer 딕셔너리에 값을 담아준 후

현재 스테이지에 머무른 플레이어의 수를 그때그때 빼주는 깔끔한 풀이입니다.

다만 list.count()의 시간복잡도가 O(N)임을 고려해야겠습니다.