[프로그래머스] Lv1 - 실패율

문제

프로그래머스 2019 KAKAO BLIND RECRUITMENT

• Lv 1. 실패율 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/42889

문제 설명

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

• 실패율은 다음과 같이 정의한다.
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

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

입출력 예 설명

입출력 예 #1
1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

• 1 번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

• 2 번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

• 3 번 스테이지 실패율 : 2/4
• 4번 스테이지 실패율 : 1/2
• 5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.
→ [3,4,2,1,5]

입출력 예 #2
모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.
→ [4,1,2,3]

코드 구현

def solution(N, stages):
    answer = [] # 정답을 리턴할 리스트

    failed_total = []           # 각 스테이지의 실패율을 계산한 값을 저장할 리스트
    stage_arrive = len(stages)  # 스테이지에 도달한 플레이어 수
    count_player = 0            # 저번 스테이지에서 이미 계산해서 다음 스테이지에서는 고려하지 않아도 되는 플레이어 수 (시작은 0)

    dictionary = dict()         # 각 스테이지 번호를 실패율의 내림차순으로 정렬하기 위해 선언한 딕셔너리

    for i in range(1, N + 1):   # 각 스테이지에 대한 실패율 계산
        failed_player = []      # 해당 스테이지에 도달했으나 아직 클리어하지 못한 플레이어들을 담을 리스트
        for j in stages:        # 해당 스테이지에서 실패한 플레이어 찾아내기
            if (j == i):        # 해당 스테이지와 번호가 같다면 도달했으나 아직 클리어 못한 플레이어임
                failed_player.append(j)

        stage_arrive = stage_arrive - count_player      # 스테이지에 도달한 플레이어 수 갱신

        if(stage_arrive == 0):      # 만약 스테이지에 도달한 유저가 없는 경우
            failed_total.append(0)  # 실패율은 0
        else:
            failed_total.append(len(failed_player) / stage_arrive)      # 실패율 계산
        count_player = len(failed_player)       # 다음 스테이지 실패율 계산을 위해 이번 실패율 계산에 사용된 플레이어 수를 미리 저장해두기

        dictionary[i] = failed_total[i-1]   # 딕셔너리에 추가 (key : 현재 스테이지 번호 i, value : 해당 스테이지의 실패율 값)

    # 모든 실패율 계산 이후
    ans_list = sorted(dictionary.items(), reverse=True, key=lambda item: item[1])   # 딕셔너리의 value값(실패율)을 기준으로 내림차순 정렬

    # 정렬된 형태가 튜플로 묶여서 리스트에 들어가있기 때문에 스테이지 번호만 추출하기 진행
    for i in ans_list:
        answer.append(i[0])     # answer 리스트에 스테이지 번호만 걸러서 추가하기

    return answer

풀이

• 한 스테이지의 실패율을 계산하고 나면 → 그 다음 스테이지에서는 그 전 스테이지 실패율 계산에 들어갔던 플레이어는 제외하고 계산하게 됨

  ex) 아래와 같은 예시라면 스테이지에 도달한 플레이어 수를 다음과 같이 계산하여 구해야함
  N : 5
  stages : [2, 1, 2, 6, 2, 4, 3, 3]

  스테이지	1	2	3	4	5
  도달 but 아직 클리어하지 못한 플레이어 수	(stages 내 1 개수) = 1	(stages 내 2 개수) = 3	(stages 내 3 개수) = 2	(stages 내 4 개수) = 1	(stages 내 5 개수) = 0
  스테이지에 도달한 플레이어 수	8	(8 - 1) = 7	(7 - 3) = 4	(4 - 2) = 2	1
  실패율	1/8	3/7	2/4	1/2	0/1

• N 만큼의 스테이지 수를 돌면서 각 스테이지의 실패율을 구해야함 → 각 스테이지에서 실패율 계산을 위한 실패율의 분자&분모 값 찾아내기

  • 도달하였으나 클리어하지 못한 플레이어 수 (→ 위 코드에서는 failed_player 리스트)
    == stages 리스트 내에서 해당 스테이지와 같은 번호를 가지고 있으면 그 스테이지에 머물러있는 것이므로 도달했으나 클리어 못한 플레이어임 (실패율의 분자값)
  • 스테이지에 도달한 플레이어 수 (→ 위 코드에서는 stage_arrive 변수)
    == 이전 스테이지들을 클리어하지 못한 플레이어 수를 제외하고 남아있는 stages 리스트의 길이
    == 현재 스테이지 기준 플레이어 수에서 이전에 계산한 도달 but 클리어하지 못한 플레이어 수가 빠진 값
    == 초기값은 무조건 stages 리스트 길이, 그 다음은 stages 길이에 이전 스테이지를 클리어하지 못한 플레이어 수 빼기, 그 뒤로는 그 값에서 계속 바로 전 스테이지를 클리어하지 못한 플레이어 수를 빼주기 (갱신해가기)

• 각 스테이지 번호의 실패율의 내림차순 정렬을 위해 딕셔너리 필요

  • 딕셔너리 key 값 == 해당 스테이지 번호
  • 딕셔너리 value 값 == 해당 스테이지의 실패율

• 실패율인 딕셔너리 value 값 기준 내림차순 정렬을 하게 되면 아래와 같은 튜플 형태로 묶여서 리스트에 들어가있음 → 따로 스테이지 번호만 추후 for문을 통해 추출함

• [(스테이지 번호, 해당 스테이지의 실패율), … ]
  ex) [(4, 1.0), (1, 0.0), (2, 0.0), (3, 0.0)] → [4, 1, 2, 3]
  

What I learned

▶️ 파이썬 딕셔너리 value값 기준 내림차순 정렬 방법

참고 : https://rfriend.tistory.com/473

sorted_list = sorted(dictionary.items(), 
					 reverse=True, 
					 key=lambda item: item[1])

▶️ 파이썬 딕셔너리 value값 기준 정렬 → 튜플형식 대신에 key만 추출하기

https://hello-bryan.tistory.com/78

sorted_list = sorted(dictionary, 
					 reverse=True, 
					 key=lambda x: dictionary[x])