[Algorithm🧬] 실패율

문제 / 풀이.py, [풀이.swift](

python

def solution(N, stages):
    # 하나 더 만들어서 0번째를 버리기로 했다.
    # 1까지 깬 사람 숫자를 헷갈리니까
    stop_count = [0] * (N+2)
    fail_ratio = [0] * (N+2)
    result = []

    
    # 해당 stage(index), 멈춘 사람 수(value) 로 하는 list 만듬.
    for stage in stages:
        stop_count[stage] += 1
        
    # 실패율 계산.
    # 해당 stage를 클리어 한 사람까지 계산해야하니까 뒤부터.
    # stage + 1 인 경우는 다 깬 사람이니까 해당 Stage 의 실패율은 계산할 필요 없어서
    # N부터 시작.
    for i in range(N, 0, -1):
        come_count = 0
        # 해당 스테이지까지 온 사람의 수를 센다.
        for j in range(N+1, i-1, -1):
            come_count += stop_count[j]
        
        # 스테이지까지 온 사람이 없으면 실패율 0으로 계산.
        if come_count == 0:
            fail_ratio[i] = 0
        else:
            fail_ratio[i] = stop_count[i] / come_count
    
        
    # 실패율에서 마지막 값은 없고,
    # 0번째 값은 계산을 편리하게 하기 위해 넣은 허수였으므로 뺀다.
    fail_ratio.pop()
    fail_ratio.pop(0)
    
    # (index, 실패율) 구조로 만들어서 실패율 기준 내림차순 정렬
    fail_ratio = list(enumerate(fail_ratio))
    fail_ratio = sorted(fail_ratio, key=lambda x:x[1], reverse=True)
    
        
    for (index, fail) in fail_ratio:
        result.append(index + 1) # 하나 빼서 0번부터 시작하고 있으므로 index에 1 더한다.
        
    return result

푸는데 35분 정도 걸렸다. 알고리즘 자체는 어렵지 않게 생각해낼 수 있었는데, enumerate, list, value 기준 sorted 쓰는게 생각이 안나서 헤매다가 결국 검색해서 찾았다. 이 부분을 잘 외워서 개선하는 것이 좋을 것 같다.

1221 JavaScript

def solution(N, stages):
    count = [0] * (N+2)
    sum = 0
    failable = []
    result = []
    
    for stage in stages:
        count[stage] += 1

    sum = count[N+1]
    for i in range(N, 0, -1):
        sum += count[i]
        ratio = count[i] / sum if sum != 0 else 0
        failable.append([i, ratio]))
    
    # 왜? reverse=True 주면 큰 index가 먼저 나올까..?
    failable = sorted(failable, key=lambda fail: fail[1])
    failable = list(map(lambda x: x[0], failable))[::-1]
    
    return failable

저번보다 조금 코드 줄은 줄였는데 sorted 가 말썽이었다. 저번이랑 똑같이 value 값 기준으로 정렬하니까 index가 큰게 먼저 나옴... 왜???? 그래서 그냥 오름차순 정렬을 하고 뒤집었다.
-> value가 같으면 key는 내림차순 되어버리는데 failable에서는 enumerate로 넣어서 원래 0번째가 n번째가 되어서 key가 뒤집혀있어서 그렇다.

수업 코드

// step 3
function solution(스테이지수, stages) {
    let 실패율 = [];
    let 유저수 = stages.length;

    for (let i = 1; i <= 스테이지수; i++) {
        let 도달한사람수 = stages.filter((user) => user === i).length;
        let 확률 = 도달한사람수/유저수;
        유저수 -= 도달한사람수;
        실패율.push({stage : i, 확률 : 확률});
    }

    // sort의 내림차순
    // b - a
    // sort의 오름차순
    // a - b
    실패율.sort((a, b) => {
        if (a.확률 === b.확률){
            return a.stage - b.stage;
        } else {
            return b.확률 - a.확률;
        }
    });

    return 실패율.map(object => object.stage);
}

220123 swift

import Foundation

func solution(_ N:Int, _ stages:[Int]) -> [Int] {
    var challengers = Array(repeating: 0, count: N+2)
    var entered = 0
    let personCount = stages.count
    var failable = [Int:Double]()
    
    
    for stage in stages {
        challengers[stage] += 1
    }
    
    for i in stride(from: N+1, to: 0, by: -1) {
        entered += challengers[i]

        if i <= N {
            if entered == 0 {
                failable[i] = 0
            } else {
                failable[i] = Double(challengers[i]) / Double(entered)
            }
        }
    }
    
    return Array(failable.keys).sorted {
        if failable[$0]! > failable[$1]! {
            return true
        } else if failable[$0]! == failable[$1]! {
            return $0 < $1
        } else {
            return false
        }
    }
}

풀려고 들어갔더니 풀다 만 흔적이 있어서 당황했다.

돌이켜보니.. Array(repeating: 0, count: N+2) [Int:Double]() stride(from: N+1, to: 0, by: -1) Array(failable.keys).sorted 이런 뭘 써야하는지는 아는데 정확하게 어떤 문법으로 써야하는지 모르는 것들 찾다가 화가 나서 됐어 안풀어 됐어 파이썬으로 다른 문제 풀어!!! 하고 버린 것 같다. 알고리즘 자체는 문제 읽고 바로 떠올렸었기 때문에 나머지 코드만 보완해서 풀었다.

그런데.. 스테이지에 도달한 사람 수가 0명일때 처리를 안해서 1,6,7,9,13,23,24,25 에서 계속 에러가 났다. 해결 완료!