문제

실패율

문제 설명

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

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

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

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

---

제한사항

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

---

입출력 예시

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]

---

문제 풀이

• 스테이지의 개수 = $N$
• 사용자의 수 = stages의 크기
  - 만약 stages의 값이 N + 1인 경우 최종 클리어
• 실패율 담을 배열 = failures

1번 스테이지의 실패율

• stages[1]만 1이고 나머지는 1 초과하므로 $\frac{1}{8}=0.125$

2번 스테이지의 실패율

• stages[1] 제외 (7)
• stages[0], stages[2], stages[4]는 2이고 나머지가 2 초과하므로 $\frac{3}{7} = 0.4285714286$

3번 스테이지의 실패율

• stages[1], stages[0], stages[2], stages[4] 제외 (4)
• stages[7], stages[8]는 3이고 나머지가 3 초과이므로 $\frac{2}{4} = 0.5$

4번 스테이지의 실패율

• stages[1], stages[0], stages[2], stages[4], stages[7], stages[8] 제외 (2)
• stages[5]는 4이고 나머지가 4 초과이므로 $\frac{1}{2} = 0.5$

5번 스테이지의 실패율

• stages[1], stages[0], stages[2], stages[4], stages[7], stages[8], stages[5] 제외 (1)
• stages[3]은 5 초과이므로 클리어하였음.
• 5번 스테이지의 실패율을 0임.

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면

[3(0.5, 낮은 번호), 4(0.5, 높은 번호), 2, 1, 5]

우선적으로 스테이지당 몇 명의 사람들이 남아있는지 확인하는 작업이 필요하다.

남아있는 사용자 수를 담을 배열(stay)이 필요하다.

[2, 1, 2, 6, 2, 4, 3, 3]을 예로 들면

stay = [0, 1, 3, 2, 1, 0, 1]

그리고 전체 사용자 수(players)와 stay를 사용하여 실패율을 구한다.

여기서 실패율(failures)은 정렬 편의성을 위해 dictionary로 사용한다.

1번 입출력 예시로 보면
1번 스테이지에 남아있는 사람(stay[1])은 1이고 전체 사용자 수(players)는 8이므로
failures[1]는 $\frac{1}{8} = 0.125$가 된다.
그 후 1번 스테이지에 남아있는 사람을 제외하고 다음 스테이지를 봐야한다.
players -= stay[1]

2번 스테이지에 남아있는 사람(stay[2])은 3이고 전체 사용자 수(players)는 7이므로
failures[2]는 $\frac{3}{7} = 0.4285714286$가 되고 2번 스테이지에 남아있는 사람을 제외하면 players = 4가 된다.

이런 식으로 계속하면 failures 딕셔너리가 완성된다.

여기서 이제 sorted()를 활용하여 정렬한다.

딕셔너리를 사용했던 이유가 여기에 있다.

sorted()를 통해 값을 정렬 기준으로 삼고 키를 반환하여 문제에서 요구하는 정보를 반환한다.

또한 sorted()는 값이 동일할 경우 기존 순서대로 유지한다.

sorted()는 기본으로 오름차순 정렬로 데이터를 반환하므로 reverse=True를 통해 내림차순 정렬을 하면 완벽하게 데이터가 나온다!

def solution(N, stages):
    # 현재 스테이지에 남아있는 사람을 담은 stay 배열
    # 인덱스: 스테이지
    # 값: 남아 있는 사람
    stay = [0] * (N + 2)

    for stage in stages:
        stay[stage] += 1

    print(stay)

    # 실패율 구하기
    failures = {}
    players = len(stages)

    # 각 스테이지를 돌면서 실패율 구하고
    # 다음 스테이지에서는 지금 스테이지의 인원 빼야함.
    for i in range(1, N + 1):
        if stay[i] == 0:
            failures[i] = 0
        else:
            failures[i] = stay[i] / players
            players -= stay[i]

    print(failures)

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

    return answer

---

느낀점

딕셔너리와 sorted()에 대해 더욱 알게 되었다.

딕셔너리 정렬

코딩 테스트 문제에서 특정 값에 대한 키나 인덱스를 정렬하도록 유도할 때 다른 자료구조보다 딕셔너리가 강력하다.

딕셔너리를 for문이나 sorted()에 넣으면 기본적으로 '키(Key)'들만 반환된다.

값을 기준으로 키를 정렬시키기 위해서는 sorted() 안에 key=lambda x: failures[x] 같이 작성한다.

내림차순 정렬을 위해서는 reversse=True로 작성한다.

파이썬에서 sorted()를 사용하면 기준이 되는 값이 동일할 경우 기존의 순서를 유지해준다.

따라서 아래와 같이 작성하면 딕셔너리 정렬이 빠르고 편리하게 될 수 있다.

# 예시: failures = {1: 0.125, 2: 0.428, 3: 0.5, 4: 0.5, 5: 0}
answer = sorted(failures, key=lambda x: failures[x], reverse=True)