프로그래머스 | 2019 KAKAO BLIND RECRUITMENT | 실패율 [파이썬 python]

프로그래머스

문제가 길기 때문에 접근법과 풀이과정에 대한 설명만 남깁니다.

 

처음 시도한 코드

def solution(N, stages):
    fail = [0] * N # 실패율
    for i in range(N):
        fail[i] = [i+1, stages.count(i+1) / sum([s>=(i+1) for s in stages])]
    return [i[0] for i in sorted(fail, key=lambda x:x[1], reverse=True)]

처음 접근한 방식은 다음과 같다.

각 단계별 실패율을 담을 리스트 fail을 0이 담긴 길이 N의 형태로 만든다.

 

그다음 for문을 통해 N개의 단계별 실패율을 구한다.

오천성 게임은 1단계부터 N단계까지 이고, fail의 인덱스는 0번부터 N-1까지이다. 그러므로 1단계는 fail[0], 2단계는 fail[1]에 담기는 것을 생각해야 한다.

각 단계의 실패율은 "스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수"로 구함을 문제에서 알려주었다.

 

이를 쉽게 해석하기 위해 1단계를 예로 들었을 때, "1단계에 위치한 플레이어 수/1단계를 통과+위치한 플레이어 수"가 실패율이 될 수 있다.

1단계에 위치한 플레이어 수를 찾기 위해서는 stages에서 1이 몇 개인지 찾으면 된다.

그러므로 리스트에서 해당 값의 개수를 구하기 위해 count 함수를 사용하였다.

그다음으로, 1단계를 통과+위치한 플레이어 수는 1보다 크거나 같은 값이 몇 개인지 세면 된다.

stages의 모든 값을 1과 비교해 1 이상이면 True를 반환하게 하는 리스트 컴프리헨션을 작성하였고, 이 리스트를 sum 하여 True의 개수로 1단계를 통과한 플레이어 수를 구하였다.

 

하지만, 우리가 구해야 하는 답은 스테이지 번호를 실패율 순으로 나열해야 하는 것인데, 단지 실패율만 구하면 해당 실패율이 몇 단계인지 파악하기 어렵다고 생각했다.

이는 위에서 언급한 fail의 인덱스는 0부터 시작하고 스테이지는 1부터 시작하는 것이 원인이다.

그래서 fail[i]에 실패율을 넣을 때, 스테이지 번호와 함께 [i+1, 실패율] 형태로 넣어주었다. i+1이 해당 스테이지 번호가 된다.

 

실패율에 따라 내림차순 정렬을 해야 하므로 [i+1, 실패율]에서 실패율이 위치한 [1] 번 인덱스를 기준으로 정렬해 주었다.

sorted의 key에 lambda 함수를 이용하여 [1] 번 인덱스를 기준으로 정렬할 수 있게 해 주었고, 정렬된 결과에서 [0] 번 인덱스인 스테이지 번호만 리턴할 수 있게 함으로써 코드 작성을 완료하였다.

하지만, 에러가 발생하면 시간초과일 것으로 생각했던 것과는 달리 런타임 에러가 발생하였다.

이는 분명히 코드에서 원인이 발생한 것인데 어떤 경우가 런타임 에러를 불러오는지 생각해 보니, N=5, stages=[4,4,4]이면 ZeroDivisionError 발생하는 것이다.

스테이지는 5단계까지 존재하지만 세명의 플레이어들은 4단계까지만 완료했기 때문에 5단계를 통과+위치한 플레이어 수는 0명이다.

그렇기 때문에 실패율을 구하는 분모인 '통과한 플레이어 수'가 0이 되어 ZeroDivisionError가 발생한 것이다.

def solution(N, stages):
    fail = [0] * N # 실패율
    for n in range(N):
        try:
            fail[n] = [n+1, stages.count(n+1) / sum([s>=(n+1) for s in stages])]
        except: # ZerodivisionError일 경우(=스테이지에 도달한 유저X) 실패율은 0
            fail[n] = [n+1, 0]
    print(fail)
    return [i[0] for i in sorted(fail, key=lambda x:x[1], reverse=True)]

ZeroDivisionError를 방지하기 위해 에러가 발생하면 except 구문을 실행하여 실패율을 0으로 정의하도록 코드를 수정하였다.

이제 더 이상 런타임 에러는 발생하지 않지만, 시간초과가 발생한다. N은 500, stages 길이는 200,000까지 가능하기 때문이다.

위 코드에서도 볼 수 있듯이 for문안에 stages를 순회하는 for문이 중첩되어 있다.

이 부분을 해결하기 위해 많은 시간을 고민해 보았다.

 

정답 코드

def solution(N, stages):
    fail = [0] * N # 실패율
    player = len(stages) # 스테이지별 유저 수
    for n in range(N):
        try:
            fail[n] = [n+1, stages.count(n+1) / player]
        except: # ZerodivisionError일 경우(=스테이지에 도달한 유저X) 실패율은 0
            fail[n] = [n+1, 0]
        player -= stages.count(n+1)
        
    return [i[0] for i in sorted(fail, key=lambda x:x[1], reverse=True)]

문제 조건에 stages의 모든 값은 1 이상이라고 주어진 것을 보고 무조건 모든 유저는 1단계를 꼭 하게 됨을 알게 되었다.

그래서 매번 stages를 순회하며 통과한 플레이어 수를 구하는 것보다 변수 하나를 가지고 연산하는 게 효율적일 것이라고 판단했다.

 

통과+위치한 플레이어 수를 의미하는 player=len(stages)로 처음 유저 수를 저장해 주었다. 처음 유저인 player는 1단계를 통과했든 못했든 경험이 있는 모든 유저로 볼 수 있다.

1이면 아직 1단계에 위치한 플레이어이고, 1 이상의 수면 이미 1단계는 해결해 다음 단계로 넘어간 유저이다.

따라서 단계(=N) 별로 for문을 돌며 매 단계마다 통과하지 못한 사람 수를 player에서 빼주면 단계별 player를 구할 수 있다.

중첩된 for문으로 인해 발생하는 시간 초과를 해결했다. 하지만 이 코드는 N이나 stages의 길이가 커지면 실행 시간은 오래 걸리는 것은 분명하다.