[프로그래머스] 실패율(python)

2021년 5월 21일 Algorithm, 프로그래머스, 실패율

2019년 카카오 블라인드 채용 출제

 

TL;DR

• 주어진 문제의 조건을 구현할 수 있는지
• 정렬을 활용할 수 있는지

문제 분석

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

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

- 1 : 구현해야 하는 실패율의 조건을 제시하고 있다.

- 5 ~ 6 : 문제 구현 시 고려해야 하는 제한사항에 대해 명시하고 있다.

   - 5번 제한사항의 경우, 실패율이 동일한 스테이지에 대한 처리 방법을 명시하고 있다.

   - 6번 제한사항의 경우, 스테이지에 도달한 플레이어가 없는 경우, 즉, 0으로 나누는 경우를 처리해야 함을 명시하고 있다.

입출력 형태

총 스테이지의 수와, 각 유저가 도달한 스테이지에 대한 정보가 주어지고 있다.

 

- N : 총 스테이지의 수를 의미한다.

- stages : 각 유저들이 도달한 스테이지를 담고 있다. 각 유저는 해당 스테이지에 머물러 있는 상태이다.

 

results가 나오는 과정을 설명하고 있다.

 

- results가 왜 주어진 예시와 같이 나오는지에 대해서 설명하고 있다.

- 실패율을 계산한 후 내림차순으로 정렬해야 한다.

풀이

def solution(N, stages):
    clears = [0] * (N + 2)
    users = [0] * (N + 2)
    scores = {}
    sorted_scores = []
    answer = []
    
    # 각 스테이지에 대해 스테이지에 도달한 플레이어(users)와 도달했으나 클리어하지 못한 플레이어(clears)를 구한다.
    for stage in stages:
        for i in range(stage, 0, -1): # 2스테이지에 도달한 사람은 1스테이지도 도달한 것이다.
            users[i] += 1
        clears[stage] += 1
        
    i = 1
    for c, u in zip(clears[1:-1], users[1:-1]): # 각 스테이지에 대한 실패율을 계산한다.
        if u == 0:
            scores[i] = 0
        else:
            scores[i] = c / u
        i += 1
        
    # 실패율을 정렬한 후 정렬된 스테이지를 정답 배열에 입력한다.
    sorted_scores = sorted(scores.items(), key=(lambda x: x[1]), reverse=True)
    for sorted_score in sorted_scores:
        answer.append(sorted_score[0])
        
    return answer

 

- 각 스테이지에 대한 정보를 토대로, 스테이지에 도달한 유저와, 도달했으나 클리어하지 못한 유저의 수를 얻어낸다.

- 유저 정보에 대한 배열(`clears`, `users`)을 N + 2 크기로 만든 이유는 주어진 스테이지를 그대로 인덱스로 활용하기 위해서이고, 모든 스테이지를 클리어한 사람들이 N + 1로 명시되기 때문이다.

 

- 0번 인덱스와 마지막 인덱스를 제외한 유저 정보 배열을 토대로, 점수를 계산한다.

- 유저가 없는 경우를 위해서 조건문을 활용하였다.

- dictionary를 사용한 이유는 정렬은 점수로 하지만, 출력은 해당 스테이지로 해야 하기 때문이다. 이 경우, key는 스테이지, value는 해당 스테이지에 대한 실패율이 된다.

 

- 얻어낸 스테이지 별 실패율을 정렬한다. `key` 옵션에 람다식을 사용하여, 계산한 실패율을 토대로 정렬을 진행한다.

- 얻어낸 정렬된 배열 `sorted_scores`는 key와 value가 튜플 쌍으로 이루어져 있다.

- 원하는 것은 스테이지에 대한 정보이기 때문에 스테이지만 얻어내어 answer에 저장한다.

개선된 풀이

- 작성한 코드의 경우, 스테이지에 대한 유저 정보를 계산하는 부분과 실패율을 계산하는 부분이 따로 적혀 있어 시간 복잡도가 매우 높다.

- 직관적인 코드를 위해서 동작되어야 하는 부분을 각각 구현하여 코드가 다소 길어졌다. 스테이지에 대한 유저 정보를 구하는 부분과 실패율을 계산하는 부분을 하나로 묶고, 정렬하고 정렬된 스테이지를 얻어내는 부분을 개선할 수 있는 여지가 있다.