|
์ฝ๋ ์์ฑํ๊ธฐ
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