[Algorithm][programmers][python3] 실패율

문제

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42889

코딩테스트 연습 - 실패율

게임 개발자 오렐리는 신규 사용자와 기존 사용자 간 스테이지 차이가 너무 커, 동적으로 시간을 늘려서 게임 난이도를 조절하기로 했다. 대부분의 로직은 쉽게 구현했으나 실패율을 구하는 부분에서 위기에 빠지고 말았다.

실패율을 다음과 같이

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

라고 정의했을 때 실패율을 구하는 코드를 완성하라.

매개변수로는 전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 주어진다.

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

 

풀이

 

핵심 알고리즘 : 딕셔너리

 

key를 스테이지 번호, value을 스테이지를 도달한 플레이어 수, 클리어 못한 플레이어의 수, 실패율로 정의.

stages 배열을 for문으로 접근하여 value을 업데이트 하면 되지 않을까?

=> 22번 테스트 케이스에서 시간 초과라는 오류가 발생한다.

=> for문으로 stages 배열에 접근하는 게 아닌 range(1, N + 1)에 접근, 딕셔너리 또한 실패율만 value으로 잡도록 하자.

클리어하지 못한 플레이어의 수는 해당 스테이지 번호와 같은 사람의 수, 

스테이지를 도달한 플레이어의 수는 스테이지의 전체 수 - 전 스테이지에서 도달하지 못한 사람의 수로 정의하고 for문 안에서 전 스테이지에서 도달하지 못한 사람의 수로 하게 되면 쉽게 실패율을 구할 수 있다.

 

 

Python 코드

 

• 테스트 케이스 22번에서 시간 초과난 코드

CHALLEGERS = 'challengers'
NOT_CLEARS = 'not_clears'
FAIL_RATE = 'fail_rate'

def solution(N, stages):
    # stage_info : 각 스테이지 별 도달한 플레이어 수, 클리어 못한 플레이어의 수, 실패율 표기
    stage_info = {i : {CHALLEGERS : 0, NOT_CLEARS : 0, FAIL_RATE : 0}
                  for i in range(1, N+1)}

    for stage in stages :
        # 사용자가 도달한 스테이지 stage와 전체 스테이지 개수 N 비교하여 최대 범위 설정
        if (stage > N) :
            max_range = N
        else :
            max_range = stage
            
        for i in range(1, max_range + 1) :
            stage_info[i][CHALLEGERS] += 1
        if (stage <= N) :  
            stage_info[stage][NOT_CLEARS] += 1
    
    for i in range(1, N + 1) :
        if (stage_info[i][CHALLEGERS] == 0) :
            stage_info[i][FAIL_RATE] = 0
        else :
            stage_info[i][FAIL_RATE] = stage_info[i][NOT_CLEARS] / stage_info[i][CHALLEGERS]
    
    # 실패율이 높은 스테이지로부터 내림차순 정렬, 같다면 스테이지 번호가 작은 순으로 정렬
    answer = sorted(stage_info.items(), key = lambda x : (-x[1][FAIL_RATE], x[0]))
    return [i[0] for i in answer] # 리스트의 0 인덱스(스테이지 번호)만 리스트로 반환

 

• 통과한 코드

def solution(N, stages):
    # answer : 각 스테이지 별(key) 실패율(value) 표기
    answer = {}
    
    # 해당 스테이지를 도달한 사람을 구하기 위한 변수
    temp = len(stages)
    
    for stage in range(1, N+1) :
        # 해당 스테이지를 클리어하지 못한 사람 수
        not_clear = stages.count(stage)
        # 해당 스테이지에 도달한 사람 수
        reach = temp
        # 다음 스테이지에서 도전자 수
        temp -= not_clear
        # 실패율 처리
        if (reach == 0) : # 스테이지에 도달한 유저가 없는 경우
            answer[stage] = 0
        else :
            answer[stage] = not_clear / reach
        
    # 높은 스테이지로부터 내림차순 정렬, 같다면 스테이지 번호가 작은 순으로 정렬
    answer = sorted(answer.items(), key = lambda x : (-x[1], x[0]))
    return [i[0] for i in answer] # 리스트의 0 인덱스(스테이지 번호)만 리스트로 반환

 

후기 및 보완할 점

 

아마 입출력 예의 해설을 좀 더 읽어보고 규칙을 찾았다면 삽질 안 하고 쉽게 해결했을 문제 같다.