스택/큐_주식가격_python
문제 설명
초 단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
제한사항
- prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
- prices의 길이는 2 이상 100,000 이하입니다.
입출력 예 설명
- 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
- 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
- 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
- 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
- 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.
접근 방법
가능한 이중 반복문을 사용하고 싶지 않았지만, while과 for 둘 다 사용하여 풀었다.
처음엔 popleft()로 pirces 배열 자체와 비교하려 하였지만, 가격이 떨어지는 경우를 찾는 것이 핵심이었기에 맨 앞 삭제한 큐를 이용해 삭제한 값과 큐를 비교하여 가격이 떨어졌을 경우의 시간을 배열에 추가하는 방식으로 풀었다.
deque 라이브러리로 배열을 큐로 변환 q의 길이가 0이 될때까지 반복한다.
변환한 q의 맨 앞의 값을 삭제한다.
삭제한 값을 이용해 큐 내부에 삭제한 값보다 작은 값이 있는지를 확인한다. 이 과정이 주식 가격이 하락한 경우이다.
q를 비교할때마다 q배열의 길이가 줄어들고, 가격이 떨어진 경우를 바로 기억하면 되는 문제이다.
스택/큐라는 타이틀이 붙어있어 가장 먼저 큐를 떠올려 풀이를 해보았다. 매번 드는 생각이지만 타이틀이 없을 경우 어떤 자료구조, 추상 자료형을 사용해 문제를 해결하면 되는지에 대한 감을 잡는 게 생각보다 어렵다고 느낀다.
자료구조를 공부하기 전의 나였다면 그냥 무조건 배열로 돌리려고 생각했을 것이다.
제한사항에서 길이는 최대 10만까지 올라가는데 이중 for문을 사용해도 문제가 풀린다고 한다.
(보통 길이 10만은 O(n^2)에서 런타임에러가 발생한다고 한다.)
내 풀이와 완전 똑같은 풀이가 있어서 놀랐다...!!!
from collections import deque
def solution(prices):
answer = []
q = deque(prices)
while len(q) > 0:
pop_price = q.popleft()
time = 0
for price in q:
# 가격이 떨어지는 경우
if pop_price > price:
time += 1
break
else:
time += 1
answer.append(time)
return answer
스택을 이용한 풀이
아래는 큐로 문제를 푼 후 스택으로 풀이한 경우 O(n)으로 해결할 수 있는 답변을 가져와봤다.
핵심은 스택에 가격을 저장하는 것이 아닌, 인덱스를 저장하는 것 (주식 가격이 처음으로 떨어지는 지점을 아직 못 찾은 가격의 index 모음)이다.
def solution(prices):
answer = [0] * len(prices)
stack = [0]
for i in range(1, len(prices)):
if prices[i] < prices[stack[-1]]:
for j in stack[::-1]:
if prices[i] < prices[j]:
answer[j] = i-j
stack.remove(j)
else:
break
stack.append(i)
for i in range(0, len(stack)-1):
answer[stack[i]] = len(prices) - stack[i] - 1
return answer
다시 한번 풀어본 풀이
코딩 테스트 연습 카테고리에서 문제를 풀다보니 이전에 풀었던 문제를 또 풀었다.
이전에 풀어봤기에 쉽게 풀었어야 하는데 어느정도 생각하는데 시간을 꽤 다시 잡아먹었다.
작성해놓고 보니 변수명만 이전 문제와 비슷햇을뿐 풀이과정이 똑같았다.
포스팅하는 것의 장점이지 않을까 싶다.
당시에도 이중 반복문으로 풀고 싶지 않다고 생각했는데 이번에도 같은 생각이었다.!!
from collections import deque
def solution(prices):
answer = []
q = deque(prices)
while q:
frist_data = q.popleft()
period = 0
for price in q:
# 가격이 떨어지는 경우
if frist_data > price:
period += 1
break
else:
period += 1
answer.append(period)
return answer시간 복잡도
앞선 문제를 풀며 반복문 하나는 반드시 O(N)이 아니라는 것을 알게 되었었다.
1. 큐를 사용한 풀이는 O(n^2)이다.
n, n-1, n-2... 을 반복하기에 N * N-1 => O(n^2-n) => O(n^2)
2. 스택을 사용한 풀이는 O(n)이라 한다는 의견이 많다.
하지만 스택을 사용해도 어차피 O(n^2)이지 않을까? 생각한다.
스택을 채우는데 O(n)을 사용하고 그 안에서 for 문에서 스택을 뒤집어 최초로 가격이 떨어질 수 없기 때문에 else break를 사용하여 시간을 단축했다고 한다.
하지만 결국 스택에서 인덱스 값을 찾아 검사를 하는 과정이 필요하며 스택의 길이가 길지 않더라도 이 과정 자체가 상수항이 굉장히 작은 O(n)이지 않을까 싶다.
결국 큐와 마찬가지로 O(n^2)이나, 큐에 비해 비교하는 횟수가 훨씬 줄어들기에 상수항이 훨씬 작은 O(n^2)이지 않을까 싶다.
같은 문제도 스택/큐 사용 여부에 따라 로직을 어떻게 작성하느냐에 따라 O(n)이 되기도 하고 O(n^2)이 될 수 있음은 확실하다.
출처 :