[2019 KAKAO BLIND RECRUITMENT] 실패율

문제

• 실패율이 높은 스테이지를 내림차순으로 리턴하기
  • 실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
  • 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저
  • 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0으로 정의
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 1 <= 스테이지 개수 N <= 500
• 1 <= 사용자 수 <= 200,000

 

풀이 (23.07.21) - 25mins

• 사용자 수가 최대 200,000 이기 때문에 log(NlogN) 이하 알고리즘으로 풀어야 한다고 생각
• stages의 각 값은 사용자가 현재 도전 중인 스테이지로, "도달했으나 아직 클리어하지 못함"에 속한다.

 

• ✅ 0으로 나누면 안되는 경우의 수에서 한 번 막힘 (런타임 에러)

테스트 9 〉통과 (23.22ms, 14.8MB)
이전 풀이보다 더 효율적인 코드! 👍

def solution(N, stages):
    logs = [ 0 for _ in range(N+2) ]
    
    # 1. 각 스테이지에 실패한 사용자 수 카운팅
    for stage in stages :
        logs[stage] += 1
    
    # 2. 실패율 계산 answer[i] = i번째 스테이지 실패율
    # i번 stage의 실패율 = logs[i] / (도전한 사용자 수)
    # i번 stage 도전한 사용자 수 = 전체 사용자 수 -  i-1번 스테이지 이하로 클리어한 사용자 수
    answer = [ 0 for i in range(N+1) ]	# 실패율
    p = len(stages)						# 전체 사용자 수
    
    for i in range(1, N+1) :
        answer[i] = logs[i] / p        
        p -= logs[i]                	# 도전한 사용자 수 카운팅
        if p == 0 :                 	# ✅ 도전한 사용자가 0이면 실패율은 0
            break

    # 3. 실패율 높은 순으로 정렬
    answer = sorted([(idx+1, x) for idx, x in enumerate(answer[1:])], key=lambda x: -x[1])
    return [idx for idx, _ in answer ]   # 스테이지 번호만 리턴

 

 

풀이 2

테스트 9 〉통과 (1602.81ms, 14.9MB)

def solution(N, stages):
    # 실패율 = 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
    answer = []
    p = len(stages)
    for i in range(1, N+1):
        if p <= 0 : 
            answer.append((i, 0))
            continue
        fail = stages.count(i)
        answer.append((i, fail / p))
        p -= fail
        
    answer = sorted(answer, key=lambda x: (-x[1], x[0]))
    print(answer)
    return [ a[0] for a in answer ]