[프로그래머스] 주식가격(Python)

jisoolee·2023년 3월 30일
0

코딩 테스트

목록 보기
9/10
post-thumbnail

문제

문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

  • prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
  • prices의 길이는 2 이상 100,000 이하입니다.

해결 과정

Deque를 이용합니다.

Deque(Double-ended queue): 양쪽 끝에서 데이터의 삽입과 삭제가 가능한 자료구조
*deque는 스택과 큐의 기능을 모두 갖고 있으며, 많은 양의 데이터를 저장할 때 메모리를 효율적으로 사용할 수 있습니다.

주식 가격이 떨어지지 않는 기간을 계산하는 방식입니다.

1트(실패/ 효율성 시간 초과)

  1. prices에서 첫번째 값을 뽑습니다.
  2. 뽑은 값을 다음 값들과 비교합니다(prices 길이 만큼). 만약 다음 값이 뽑은 값보다 작을 경우에는 time+1, 반복문을 중지하고 큰 경우에는 계속 time+1을 합니다.
  3. 반복문이 끝난 후, time 값을 result에 넣습니다.
  4. 2, 3의 과정을 prices가 모두 없어질 때까지 반복합니다.

Code

from collections import deque

def solution(prices): 
    result = []
    prices = deque(prices)
    while prices:
        time = 0
        p = prices.popleft()
        for i in range(len(prices)):
            if p > prices[i]:
                time += 1
                break
            time += 1
        result.append(time)
            
    return result

테스트 케이스는 모두 통과했으나 효울성 테스트에서 시간 초과로 문제를 해결하지 못했습니다.

위 코드의 시간 복잡도는 O(n^2) 입니다.

문제점

for 루프에서 len(prices) 를 사용했기 때문에 매번 prices의 길이를 구해야됩니다. 또한, 반복문을 돌며 prices[i]를 찾는 부분도 시간 초과에 한 몫 한 것 같습니다.

2트(성공)

range가 아닌 리스트 반복문으로 변경했습니다.

Code

from collections import deque

def solution(prices):
    result = []
    prices = deque(prices)
    while prices:
        time = 0
        p = prices.popleft()
        for i in prices:
            time += 1
            if p > i:
                break
        result.append(time)
    return result

0개의 댓글