[Algorithm๐Ÿงฌ] ์‹คํŒจ์œจ

22748 ๋‹จ์–ด algorithmalgorithm

๋ฌธ์ œ / ํ’€์ด.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 ์—์„œ ๊ณ„์† ์—๋Ÿฌ๊ฐ€ ๋‚ฌ๋‹ค. ํ•ด๊ฒฐ ์™„๋ฃŒ!

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ