[Programmers/Lv. 1] 실패율 (2019 KAKAO BLIND RECRUITMENT, Python)

📎 링크

---

프로그래머스

 

 

🤔 문제설명, 제한사항, 입출력 예

---

실패율을 구하는 코드를 완성하라는 문제이다.
실패율은 다음과 같이 정의한다. "스테이지에 도착했으나, 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수"

전체 스테이지의 개수 N과, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열이 같이 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 구하라는 문제이다.

 

 

🤔 내가 생각한 풀이 과정 (1) - 런타임 에러 코드

---

문제에 나와있는 예시 순서대로 따르고자 했다.

우선, count() 함수를 이용해 stage별로 아직 클리어하지 못한 사용자의 수를 count_list라는 별도의 리스트로 만들어줬다.
그리고, count_list를 반복하면서 리스트의 슬라이싱 기능을 이용해 각 스테이지별로 "스테이지를 클리어하지 못한 사용자의 수 / (전체 사용자 수-이전 스테이지를 클리어하지 못한 사용자 수)"를 구해주며, 실패율을 구해줬다.
구한 실패율(딕셔너리의 Value)을 바탕으로 딕셔너리를 정렬시켜, Key값을 리스트 컴프리헨션으로 만들어 반환시켰다.

코드를 보면 알겠지만, 내 코드는 3번의 반복문과 정렬하는 sorted() 함수까지 굉장히 높은 시간 복잡도를 갖고 있었다.
당연히 런타임 에러가 발생했고, 코드를 다시 정리해주기로 한다.

def solution(N, stages):
    count_list = [stages.count(i) for i in range(1, N+1)]
    fail_ratio = {i+1: (v / (len(stages)-sum(count_list[:i]))) for i, v in enumerate(count_list)}
    sorted_dict = sorted(fail_ratio.items(), key= lambda item:item[1], reverse=True)
    return [i[0] for i in sorted_dict]

 

 

🤔 내가 생각한 풀이 과정 (2) - 성공 코드

---

시간 복잡도를 잡아먹는 코드들을 줄이거나, 분기처리를 해주어서 새로 도전했다.

1. 반복을 할 때마다 stages의 길이를 구하지 않고, player라는 변수에 길이를 저장해서 계속적으로 활용할 수 있도록 처리했다.
2. 스테이지에 남아있는 사용자 수가 0일 때의 값을 0으로 바로 지정할 수 있도록 해 불필요한 0 나누기 연산을 하지 않도록 분기처리했다.
3. 따로, 값을 구하기 위한 count_list를 별도로 만들지 않고 바로 연산을 수행하도록 했으며, 최종 결괏값을 return 할 때도 lambda 함수를 사용해서 코드를 작성했다.

결론, 시간 복잡도와 코드 길이는 상관이 없다.
무조건 짧은 코드를 쓰는 것이 좋은 것이 아니라, 불필요한 연산이나 반복되는 연산을 생략하도록 코드를 짜는 것이 좋은 알고리즘이다.

def solution(N, stages):
    player = len(stages)
    fail_ratio = {}
    
    for i in range(1, N+1):
        # 스테이지에 남은 사용자 수가 0이 아닐 때
        if player != 0:
            fail_ratio[i] = stages.count(i) / player
            player -= stages.count(i)
       
        # 스테이지에 남은 사용자 수가 0일 때
        else:
            fail_ratio[i] = 0

    return sorted(fail_ratio, key=lambda x: fail_ratio[x], reverse=True)