๐ฉ๐ป๐ป๋ฌธ์ ์ค๋ช
[์ด์ฝํ Ch14-25] ์คํจ์จ (์ ๋ ฌ)
โ๏ธIdea Sketch
๋ฌธ์ ์์ฝ
์คํจ์จ = ์คํ ์ด์ง์ ๋๋ฌํ์ผ๋ ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์ / ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
์คํจ์จ์ด ๋์ ์คํ ์ด์ง๋ถํฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์คํ ์ด์ง์ ๋ฒํธ๊ฐ ๋ด๊ฒจ์๋ ๋ฐฐ์ด์ return ํ๋ผ.
์๊ฐ๋ณต์ก๋
์คํ ์ด์ง์ ๊ฐ์ N์ 500 ์ดํ์ด๊ณ , stages์ ๊ธธ์ด๋ 200,000 ์ดํ์ด๋ค. 500 x 200,000๋ 1์ต์ด๊ธฐ ๋๋ฌธ์ ์๊ฐ์ด๊ณผ๊ฐ ๋ ๊ฒ์ด๋ผ ์์ํ๋ค. ํ์ง๋ง ์๊ฐ์ด๊ณผ๊ฐ ๋์ง ์์๋ค. ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด์ ์๊ฐ 0๋ช ์ธ ๊ฒฝ์ฐ, count()๋ฅผ ํ์ง ์๋๋ค. ์ด ์ ๋๋ฌธ์ ํต๊ณผํ๋ค๊ณ ์๊ฐํ๋ค.
a.count(x)
๋ฆฌ์คํธ a์์ x๊ฐ ๋ช๊ฐ ์๋์ง countํ๋ค. countํ๊ธฐ ์ํด ๋ฆฌ์คํธ a๋ฅผ ์ ์ฒด ํ์ ํด์ผ ํ๋ฏ๋ก ์๊ฐ๋ณต์ก๋๋ O(n)์ด๋ค. stages.count()๋ ๋ฆฌ์คํธ stages๋ฅผ ์ ์ฒด ํ์ํ๋ค.
sort(), sorted()
ํ์ด์ฌ์ ๊ธฐ๋ณธ ์ ๋ ฌ ๋ผ์ด๋ธ๋ฌ๋ฆฌ์ธ sorted()์ sort()ํจ์๋ฅผ ์ ๊ณตํ๋ค. ๋ณํฉ ์ ๋ ฌ์ ๊ธฐ๋ฐ์ผ๋ก ๋ง๋ค์ด์ก๋๋ฐ, ๋ณํฉ ์ ๋ ฌ์ ์ผ๋ฐ์ ์ธ ๊ฒฝ์ฐ ํต ์ ๋ ฌ๋ณด๋ค ๋๋ฆฌ์ง๋ง ์ต์
์ ๊ฒฝ์ฐ์๋ ์๊ฐ ๋ณต์ก๋ O(nlogn)์ ๋ณด์ฅํ๋ค.
์๊ณ ๋ฆฌ์ฆ : ์ ๋ ฌ
โ๏ธ๋ด ์์ค์ฝ๋
- clear : ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์
- ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์๊ฐ 0๋ช ์ธ ๊ฒฝ์ฐ, ์คํจ์จ์ 0์ด๋ค.
- ์คํ ์ด์ง์ ๋๋ฌํ ํ๋ ์ด์ด ์๊ฐ 1๋ช ์ด์์ธ ๊ฒฝ์ฐ, ์์ง ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด์ ์๋ฅผ count ํ๋ค.
- clear๋ฅผ ๊ฐฑ์ ํ๋ค. ์ง๊ธ ์คํ ์ด์ง๋ฅผ ํด๋ฆฌ์ดํ์ง ๋ชปํ ํ๋ ์ด์ด๋ ๋ค์ ์คํ ์ด์ง์ ๋๋ฌํ์๋ฆฌ ๋ง๋ฌดํ๋ค.
์ ์ฒด ์ฝ๋
def solution(N, stages):
queue = []
clear = len(stages)
for stage in range(1, N+1):
if clear == 0:
queue.append((0, stage))
else:
fail = stages.count(stage)
queue.append((fail / clear, stage))
clear -= fail
queue.sort(key = lambda x: -x[0])
return [queue[i][1] for i in range(N)]
'ํ์ด์ฌ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ด์ฝํ Ch16-32] ์ ์ ์ผ๊ฐํ (DP) (0) | 2022.04.19 |
---|---|
[์ด์ฝํ Ch13-22] ๋ธ๋ก ์ด๋ํ๊ธฐ (BFS) (0) | 2022.04.05 |
[์ด์ฝํ Ch13-15] ํน์ ๊ฑฐ๋ฆฌ์ ๋์ ์ฐพ๊ธฐ (BFS) (0) | 2022.03.22 |
[์ด์ฝํ Ch13-18] ๊ดํธ ๋ณํ (์ฌ๊ท) (0) | 2022.03.22 |
[์ด์ฝํ Ch12-14] ์ธ๋ฒฝ ์ ๊ฒ (๊ตฌํ) (0) | 2022.03.17 |