[프로그래머스] 실패율 (KAKAO BLIND RECRUITMENT) - Python

2019 KAKAO BLIND RECRUITMENT - Lv1.

 

🌵 문제

---

 

https://school.programmers.co.kr/learn/courses/30/lessons/42889

프로그래머스

 

 

🚀 풀이

---

문제를 분석하면 다음과 같습니다.

N: 전체 스테이지의 개수

stages: 게임을 이용하는 사용자의, 현재 멈춰있는 스테이지 번호가 담긴 배열

stages의 길이: 유저 수

실패율의 분모: 처리 안된 (남은) 유저 수

실패율의 분자: 현재 체크하고 있는 stage의 수

---

💡 첫 번째 작성한 풀이 코드는 아래와 같습니다. 

def getReversedRatioArr(arr):
    arr.sort(key=lambda ratio: (-ratio[1], ratio[0]))  # 1st 실패율, 2nd 스테이지 작은 순으로 정렬
    result = []
    for tuple in arr:
        result.append(tuple[0])
    return result

def solution(N, stages):
    stages = sorted(stages, reverse=True)  # 정렬, 기준 정할 때 용이하고 앞 뒤만 보기 위함 (200,000)
    failRatio = []
    for stage in range(1, N + 1):  # 스테이지 별로 살펴보기 (500)
        if stage != stages[-1]:  # 해당 스테이지에 도달한 유저가 없는 경우: 실패율 0
            failRatio.append((stage, 0))
            continue
        if stages[0] == stages[-1]:  # 해당 스테이지에 도달한 유저 있는데 (앞에서 걸러짐), 전부 다 클리어 하지 못한 경우: 실패율 1
            failRatio.append((stage, 1))
            continue
        cnt = 0  # 해당 스테이지 클리어 하지 못한 유저 수
        for i in range(len(stages) - 1, -1, -1):
            if stages[i] != stage:
                break
            cnt += 1
        failRatio.append((stage, cnt / len(stages)))
        stages = stages[:-1 * cnt]
    return getReversedRatioArr(failRatio)

 

stage를 돌면서 반복문 내부에서 클리어하지 못한 유저 수를 세고 있습니다. 한 단계가 지날 때마다 클리어하지 못한 유저를 제거해주고 있어서 문제를 맞추는데 주어진 테케는 통과하긴하지만,

대략 500 * 200,000까지 시간 복잡도가 뛸 수 있어서 해당 스테이지를 클리어하지 못한 유저 수가 많을 경우 (아래 반복문에서 걸리는게 많은 경우) 위험하겠다고 생각했습니다. 🥲

for i in range(len(stages) - 1, -1, -1):
    if stages[i] != stage:
        break
    cnt += 1

 

---

그래서 반복문을 여러 번 쓸 수는 있어도 중첩해서 사용하지는 말아야 할 것 같아, 해시 테이블과 같은 방식으로 각 단계별로 유저 수를 세고 메모해두는 방식을 선택했습니다. 

 

💡 두 번째 작성한 풀이 코드는 아래와 같습니다. 

def getReversedRatioArr(arr):
    arr.sort(key=lambda ratio: (-ratio[1], ratio[0]))  # 1st 실패율, 2nd stage로 정렬
    result = []
    for tuple in arr:
        result.append(tuple[0])
    return result

def refactorSolution(N, stages):
    totalUserNum = len(stages)
    failRatio = [0] * (N + 1)  # 1부터 N까지 (인덱스 0 비워둠)
    # 각 스테이지마다 몇 명 있는지 체크, 인덱스: key, 요소: value 꼴의 해시 테이블처럼 처리
    for stage in stages:
        # 막판까지 다 깬 유저는 실패율에 영향 X
        if stage == N + 1:
            continue
        failRatio[stage] += 1  # 스테이지별 인원 체크를 위함
    # 단계마다 실패율 체크 (1단계 ~ N단계)
    for i in range(1, N + 1):
        currStageUser = failRatio[i]
        if totalUserNum == 0:
            break
        failRatio[i] = (i, failRatio[i] / totalUserNum)
        totalUserNum -= currStageUser
    # totalUserNum이 0이 되어 실패율을 비율꼴로 나타내지 못한 요소들 처리
    for i in range(N + 1):
        if failRatio[i] == 0:
            failRatio[i] = (i, 0)
    return getReversedRatioArr(sorted(failRatio[1:], key=lambda ratio: (-ratio[1], ratio[0])))