[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 ์์ ๊ณ์ ์๋ฌ๊ฐ ๋ฌ๋ค. ํด๊ฒฐ ์๋ฃ!
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm๐งฌ] ์คํจ์จ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@ddosang/Algorithm-์คํจ์จ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค