Search

ํ—ˆ์ง„ํ˜

2.๋ฌธ์ œ์ด๋ฆ„
3. ์ˆ˜ํ–‰์‹œ๊ฐ„[์ดˆ(s)]
1104
์ข‹์•„์š” ๋ˆ„๋ฅด๊ธฐ
์ข‹์•„์š” ์ˆ˜
: 0
5 more properties
| ์ฝ”๋“œ ์ž‘์„ฑํ•˜๊ธฐ
from collections import deque def solution(prices): answer = [] queue = deque(prices) # print(queue) while queue: price = queue.popleft() time = 0 for num in queue: time += 1 if price > num: break answer.append(time) # print(answer) return answer
Python
๋ณต์‚ฌ
| ์ฝ”๋“œ ์„ค๋ช…ํ•˜๊ธฐ
์ ‘๊ทผ๋ฐฉ๋ฒ•
1.
์ด์ค‘ํฌ๋ฌธ ์‚ฌ์šฉํ•ด์„œ ๋น„๊ตํ•˜๊ธฐ
a.
์ œํ•œ์‚ฌํ•ญ โ€ข prices์˜ ๊ธธ์ด๋Š” 2 ์ด์ƒ 100,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
b.
100000*100000 โ€”> ์‹œ๊ฐ„๋ณต์žก๋„ ์ดˆ๊ณผํ• ๊ฒŒ ๋ถ„๋ช…ํ•จ
2.
deque๋กœ ๋งจ ์•ž์˜ ๊ฐ’๋ถ€ํ„ฐ ํ•˜๋‚˜ํ•˜๋‚˜ ๋ฝ‘์•„์„œ ๋น„๊ตํ•˜๊ธฐ
a.
stack์€ ๋งจ ์•ž์˜ ๊ฐ’์„ ๋ฝ‘์œผ๋ ค๋ฉด O(N) โ€”> stack.pop(0)
b.
deque๋Š” ๋งจ ์•ž์˜ ๊ฐ’์„ ๋ฝ‘์œผ๋ ค๋ฉด O(1) โ€”> deque.popleft()
3.
๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ๋‹ค์Œ ๊ฐ’์„ ๋น„๊ตํ•  ๋•Œ๋งˆ๋‹ค ์‹œ๊ฐ„ 1์ดˆ๋ฅผ ์ถ”๊ฐ€ํ•ด์ฃผ๊ณ , ๋งŒ์•ฝ ๊บผ๋‚ธ ๊ฐ’๋ณด๋‹ค ํฐ ๊ฐ’์ด ๋‚˜์˜จ๋‹ค๋ฉด break