Search

์กฐ์˜ˆ์ง€

2.๋ฌธ์ œ์ด๋ฆ„
3. ์ˆ˜ํ–‰์‹œ๊ฐ„[์ดˆ(s)]
3600
์ข‹์•„์š” ๋ˆ„๋ฅด๊ธฐ
์ข‹์•„์š” ์ˆ˜
: 0
5 more properties
| ์ฝ”๋“œ ์ž‘์„ฑํ•˜๊ธฐ
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๋ฅผ ์ด์šฉํ•ด์„œ ์œ ์ง€๋œ ๊ธฐ๊ฐ„์„ ๊ณ„์‚ฐํ•œ๋‹ค.