๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿ‘จโ€๐Ÿ’ป ๊ธฐ๋Šฅ ๊ฐœ๋ฐœ ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ

๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

import math

def solution(progresses, speeds):
    answer = []
    progresses = [math.ceil((100-a)/b) for a, b in zip(progresses, speeds)]
    front = 0
    for idx in range(len(progresses)):
        if progresses[front] < progresses[idx]:
            answer.append(idx-front)
            front = idx
    answer.append(len(progresses)-front)
    return answer

์Šคํƒstack/ํqueue ์ž๋ฃŒ๊ตฌ์กฐ์— ์†ํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์šฐ์„  progresses์™€ speeds๋กœ ๋‚˜๋ˆ„์–ด์ง„ ๋‘ list๋ฅผ ํ•˜๋‚˜์˜ list๋กœ ๋งŒ๋“ค์–ด๋ด…์‹œ๋‹ค. ํ•ด๋‹น list์—๋Š” ๊ฐ ์ž‘์—…๋ณ„ ์™„๋ฃŒ๋˜๊ธฐ๊นŒ์ง€(>100%) ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์— ๋Œ€ํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๊ทธ์— ๋Œ€ํ•œ ์ฝ”๋“œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

progresses = [math.ceil((100-a)/b) for a, b in zip(progresses, speeds)]

๋‹ค์Œ์œผ๋กœ ํ•ด๋‹น list๋ฅผ ํ™•์ธํ•˜๋ฉด์„œ ๊ฒฐ๊ณผ๊ฐ’์„ ์ฐพ์•„์•ผํ•ฉ๋‹ˆ๋‹ค. ์‰ฝ๊ฒŒ ์ƒ๊ฐํ•˜๋ฉด ์ „์ฒด for loop๋ฅผ ๋Œ๋ฉด์„œ ๋งจ ์•ž์˜ ๋ฐ์ดํ„ฐ๋ณด๋‹ค ์ž‘์€ ์ง€ ํ™•์ธํ•˜๋Š” for loop๋ฅผ ๋‹ค์‹œ ์จ์„œ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(n^2)๊ฐ€ ๋˜์–ด ํŠน์ • ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์—์„œ ์‹œ๊ฐ„ ์ดˆ๊ณผ๋ฅผ ๋ฐ›๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ๊ทธ ๋ณด๋‹ค ๋‚ฎ์€ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๋Š” ๋ฐฉ์‹์œผ๋กœ ์ฝ”๋“œ๋ฅผ ์งœ์•ผํ•ฉ๋‹ˆ๋‹ค.

for idx in range(len(progresses)):
    if progresses[front] < progresses[idx]:
        answer.append(idx-front)
        front = idx
answer.append(len(progresses)-front)

์ €๋Š” ๋‹จ ํ•œ ๋ฒˆ๋งŒ ๋ฐฐ์—ด์„ ๋Œ๊ฒŒํ•˜์—ฌ ์ด ์•ˆ์— ๋๋‚ด๋„๋ก ์ฝ”๋“œ๋ฅผ ์งฐ์Šต๋‹ˆ๋‹ค. ๋Œ€์‹  front ๊ฐ’์„ ๊ณ„์† ์—…๋ฐ์ดํŠธ ํ•˜๋ฉด์„œ ๋งจ ์•ž์— ์žˆ๋Š” ์ž‘์—…์ด ๋ฌด์—‡์ธ์ง€ ํ™•์ธ ํ•  ์ˆ˜ ์žˆ๊ฒŒํ–ˆ์Šต๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ์งœ๋ฉด ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ O(n)์ด ๋˜์–ด ์‹œ๊ฐ„ ์ดˆ๊ณผ๋ฅผ ๋ฐ›์ง€ ์•Š๊ณ  ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

Written with StackEdit.

๋ฐ˜์‘ํ˜•