[Programmers][Py] 실패율

✅ 문제

문제 바로가기

✅ 나의 풀이

1. 실패율 구하기
2. 실패율을 정렬
3. 정렬된 순서로 스테이지 번호를 담은 배열 리턴

def solution(N, stages):
    
    # counter 초기화
    counter = {i:0 for i in range(N+2)}
    # counter 생성
    for i in stages:
        counter[i] += 1
    
    # 실패율 계산
    arr = []
    a = len(stages)
    for s in range(1, N+1):
        
        a = a - counter[s-1]
        b = counter[s]
        
        if a ==0: 
            rate = 0
        else:
            rate = b / a
        
        arr.append((s, rate))
        print(s, a, b)
    
    # 실패율 높은 순서대로 정렬
    arr.sort(key = lambda x:x[1], reverse = True)
    
    # 리턴값 형식으로 만들기
    returns = []
    for i in arr:
        returns.append(i[0])
    
    return returns 

실패율
= $\frac{\text{스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수}}{\text{스테이지에 도달한 플레이어 수}}$

1️⃣ 각 스테이지 별 멈춰있는 플레이어 수 구하기

stages를 이용하여 각 스테이지에 도달한 플레이어 수를 나타내는 딕셔너리 counter를 만든다. 아래는 예시이다.

입출력 예시

N	stages	result
5	[2, 1, 2, 6, 2, 4, 3, 3]	[3, 4, 2, 1, 5]

• stages
  게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열

  stages = [2, 1, 2, 6, 2, 4, 3, 3]

• counter = {스테이지 번호: 해당 스테이지에 도달해있는 사용자 수}

  counter = {
              1: 1,
              2: 3,
              3: 2,
              4: 1,
              5: 0,
              6: 1
             }
  

2️⃣ 실패율 구하기

간단하게 표현하기 위해,
실패율 = $\frac{\text{스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수}}{\text{스테이지에 도달한 플레이어 수}}$ = $\frac{b}{a}$ 라고 가정한다.

전체 스테이지의 개수가 5인 게임의 스테이지 1의 실패율을 구해보자.

a = counter[1] + counter[2] + ... + counter[6]
  = stages 배열의 길이(전체 플레이어 수)

b = counter[1]

스테이지 2의 실패율을 구해보자.

a = counter[2] + ... + counter[6]
  = 스테이지 1의 a값 - counter[1]

b = counter[2]

스테이지 3의 실패율을 구해보자.

a = counter[3] + ... + counter[6]
  = 스테이지 2의 a값 - counter[2]

b = counter[3]

따라서 실패율은 다음과같이 정의할 수 있다.

실패율 = $\frac{counter[s]}{a - counter[s-1]}$

(a는 이전 스테이지의 a값, a의 초기값은 전체 플레이어 수)

최종적으로 리턴하는 값은 실패율이 높은 스테이지 번호들이므로,
(스테이지번호, 실패율)의 형식으로 배열에 저장한다.

arr.append((s, rate))

3️⃣ 실패율 높은 순서대로 정렬하기

정렬 조건

• 1. 실패율이 높은 순서대로
• 2. 실패율이 같을 경우, 작은번호의 스테이지가 먼저 오도록

이전의 실패율을 구하는 for문에서는 스테이지 1부터 스테이지 N까지의 실패율을 순서대로 배열에 저장하였다.
이미 작은번호의 스테이지부터 정렬된 상태이므로 실패율이 높은 순서대로만 정렬해주면 된다.

	# 실패율 높은 순서대로 정렬
    arr.sort(key = lambda x:x[1], reverse = True)

4️⃣ 스테이지 번호 배열 리턴하기

최종 리턴되는 값은 실패율이 아니다. 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 리턴해준다.

    # 리턴값 형식으로 만들기
    returns = []
    for i in arr:
        returns.append(i[0])
    
    return returns 

Comment

알고리즘 자체는 어렵지 않게 생각해낼 수 있었지만, 이것을 코드로 구현하는 것이 어려웠다. 실패율을 기준으로 정렬하지만, 최종적으로 구하는 값은 실패율이 아닌 스테이지 번호여서 이 두가지의 값을 함께 저장하는 방법에 대해 고민이 필요했다.