[Programmers] stock price.py (stack/queue)

#. Problem

https://programmers.co.kr/learn/courses/30/lessons/42584

* The copyright in this matter is in Programmers

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 

가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. prices에서 순차적으로 한 요소씩 n번째 요소까지 주식 가격의 대소를 비교

  2. 비교할 때마다 1초가 증가하고, 자신보다 작은 가격을 발견 시 break

#. Code

1 2 3 4 5 6 7 8 9 10

def solution(prices):     answer = []     for prc in range(0, len(prices)):         sec = 0         for prc2 in range(prc+1, len(prices)):             sec += 1             if prices[prc] > prices[prc2]:                break         answer.append(sec)     return answer

cs

  - 이중 반복문을 사용하여 순차적으로 주식 가격의 대소를 비교

#. Others code

1 2 3 4 5 6 7 8 9 10

def solution(prices):     answer = [0] * len(prices)     for i in range(len(prices)):         for j in range(i+1, len(prices)):             if prices[i] <= prices[j]:                 answer[i] += 1             else:                 answer[i] += 1                 break     return answer

cs

  - 같은 방식의 solution이지만, answer list를 0으로 prices의 크기만큼 초기화

    (sec변수와 append함수를 사용하지 않음으로 코드가 더 간결)

    복잡도 O(N^2)

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()
        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1
 
        answer.append(count)
    return answer

  - 방식은 비슷하지만 deque를 사용하여 이중 반복문보다는 더 빠른 방법