|
์ฝ๋ ์์ฑํ๊ธฐ
def solution(prices):
answer = [0] * len(prices)
stack = []
for idx, price in enumerate(prices):
while stack:
if stack[-1][1] > price:
node = stack.pop()
answer[node[0]] = idx - node[0]
else:
break
stack.append((idx, price))
for node in stack:
answer[node[0]] = len(prices) - 1 - node[0]
return answer
Java
๋ณต์ฌ
|
์ฝ๋ ์ค๋ช
ํ๊ธฐ
์ฃผ์ ๊ทธ๋ํ๋ ์ฐ์์ ์๋ก ๋ํ๋๋ค. ๋ฌธ์ ์์ ์ด๋ค ์์ ์ ๊ฐ๊ฒฉ์ด ์ ์ ์ผ๋ก ์ ์ง๋๋ ๊ธฐ๊ฐ์ ๋ฌผ์ด๋ณด์๋ค.
์ด๋ ํ ์ง์ ์์ ๊ด์ฌ์ด ์๋ ๋ถ๋ถ์ ๋นจ๊ฐ ๋ถ๋ถ์ด๋ค. ํ์ฌ ๊ฐ๊ฒฉ๋ณด๋ค ๋ฎ์ ๋๋ ๊ด์ฌ ๋์์ด ์๋๋ค. ๊ทธ๋ฆฌ๊ณ ํ์ฌ ๊ฐ๊ฒฉ๋ณด๋ค ๋์ง๋ง ์ด๋ฏธ ๋ฎ์ ๊ตฌ๊ฐ์ ์ง๋ฌ๋ค๋ฉด ๋ฎ์ ๊ตฌ๊ฐ์์ ์ด๋ฏธ ์ฒ๋ฆฌ (๋ต์ด ๋์ด) ๋์์ ๊ฒ์ด๋ค.
๋นจ๊ฐ๋ถ๋ถ์ ๋์์ ๋ค๋ก ํ๋์ฉ ๋ณด๋ฉด์ ํ์ฌ ๊ฐ๊ฒฉ๋ณด๋ค ๋์ผ๋ฉด ๋ต์ด ๋์ค๊ณ , ๊ฐ์์ง๋ฉด ๋์ด์ ๋ณผ ํ์๊ฐ ์์ด์ง๋ค. (์์ ์ด์ ๋๋ฌธ์) ๋ฐ๋ผ์ ๋ง์ง๋ง๋ถํฐ ํ๋์ฉ ๋ณด๋ฉฐ ๊ฐ์ด ๊ฐ์์ง๋ฉด ๋ฉ์ถ๋ฉด ๋๋ค. ์ด๋ฏธ ์์์ง ๊ฐ๋ค์ ์์๋๋ก ๋ณด๊ธฐ๋๋ฌธ์ stack์ ์ฌ์ฉํ ์ ์๋ค.
prices์ ๊ฐ๋ค์ ์ํํ๋ฉฐ stack์ ๋ฃ๊ธฐ ์ ์ ์ด์ ์ stack์ ๋ค์์๋ถํฐ ํ์ธํ๋ฉฐ ๊ธฐ๊ฐ์ ๊ณ์ฐํ๊ณ stack์์ ์ ๊ฑฐํ๋ค.
๊ทธ๋ผ stack์๋ ๋
ธ๋๋ถ๋ถ๋ง ๋จ๊ฒ๋ ๊ฒ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ๊ฐ๊ฒฉ์ด ๋ ๋จ์ด์ง๋ค๋ฉด ์ค์ ํ์ดํ๋ฅผ ๊ธฐ์ค์ผ๋ก ํ์ธํ๋ฉฐ ์ด๋ณด๋ค ๋
ธ๋์ ๊ฐ์ฅ ๋ค๋ถํฐ ํ์ดํ์ ๊ฐ๊ฒฉ์ด ๊ฐ์์ง๋ ๋ถ๋ถ๊น์ง ํ์ธํ๋ค.
๋ง์ง๋ง๊น์ง ์ฒ๋ฆฌ๋์ง ์์ ๊ฐ๋ค์ด stack์ ๋จ์์์ ๊ฒ์ด๋ฉฐ ์ด๋ค์ price์ ๊ธธ์ด-1๋ฅผ ์ด์ฉํด์ ์ ์ง๋ ๊ธฐ๊ฐ์ ๊ณ์ฐํ๋ค.