ํ์ด
์ผ๋จ, 200,000์ด๋ผ์ n^2์ ์๋๋ค. ๊ทธ๋ฌ๋ฉด ํ๋ฒ์ ๊ฐ์ผํ๋๋ฐ, ์ด ๋, ์ ์ดํด๋ณด๋ฉด, ํด๋น ์คํ ์ด์ง์์์ ์คํจ์จ์ stage์์กด ์/stage ํต๊ณผ์๋ก ์ ์๋๋ค. ํต๊ณผ์์ ๊ฒฝ์ฐ 4์คํ ์ด์ง์ ์๋ ๊ฒฝ์ฐ ์ด์ 1, 2, 3์คํ ์ด์ง์ ์์ ๋ ๋ชจ๋ ์นด์ดํธ๊ฐ ๋๊ธฐ ๋๋ฌธ์ ์ด๋ถ๋ถ์ ์ ์ดํด์ผ ํ๋ค.
์ฆ, ํ์ฌ ์คํ ์ด์ง์ ์๋ ์ / ํ์ฌ ์คํ ์ด์ง๋ณด๋ค ํฐ ์คํ ์ด์ง์ ์๋ ์ฌ๋์ ๊ฐ ์คํจ์จ์ด๋ค. ์ฌ๊ธฐ๊น์ง ๋๋ฌํ๋ค๋ฉด, ์ด๋ป๊ฒ ํ๋ฉด ํฐ ์คํ ์ด์ง ์๋ฅผ ์ฝ๊ฒ ๊ตฌํ๋์ง ์๊ฐํด๋ณผ ์ ์๋๋ฐ, ์ ๋ ฌ์ ํ๊ฒ ๋๋ฉด ํฌ์ธํฐ๋ฅผ ์ญ ์ด๋ํ๋ฉด์ ํ๋ฒ์ ํ์ด๊ฐ ๊ฐ๋ฅํ๋ค.
๋ง๋ค. 0์ธ๊ฒฝ์ฐ ์ฒ๋ฆฌ์ํด์ฃผ์ด์ผ ํ๋ค.
Code
def solution(N, stages):
success = dict([[x, 0] for x in range(1,N+2)])
tries = dict([[x, 0] for x in range(1,N+2)])
stages.sort()
i = 0
stage_num = 1
while i < len(stages):
if stages[i] == stage_num:
success[stage_num] += 1
i += 1
else:
tries[stage_num] = len(stages)-i
stage_num += 1
fail_ratio = []
for num in range(1, N+1):
if success[num]+tries[num] == 0:
fail_ratio.append([num, 0])
else:
fail_ratio.append([num, success[num]/(success[num]+tries[num])])
fail_ratio = sorted(fail_ratio, key=lambda x: (x[1], -x[0]), reverse=True)
return [x[0] for x in fail_ratio]