(프로그래머스) 주식가격 _ python

문제

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

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

제안 사항

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

입출력 예

prices                                                                                          return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

문제풀이 (문제에 대한 해석 접근법)

이 문제는 코드 작성보다 문제 해석 자체를 이해하는 것이 어려웠다.

테스트케이스를 만들어 문제에 적용하면서 최대한 이해해보려고 했다.

 

문제에 대한 해석

- 테스트케이스 [1,2,3,2,1,1] 배열의 길이는 6.   6초동안의 주식 기록을 담았다.

  - > 즉, 배열 리스트의 길이는 주식 기록의 초를 의미한다. 

 

- 현재 인덱스 초 시점의 주가보다 떨어진 주가가 될 때까지 얼마의 기간인 걸렸는지 연산해 반환하는 것이다.

 

(1) 1초 시점의 주가는 1이다. 그리고 1보다 떨어진 주가는 없다.

6초동안의 측정이므로, 1초 시점부터 6초까지 5초 유지한다고 말할 수 있다.

[4]

 

(2) 2초 시점의 주가는 2이다. 그리고 현재주가 2보다 떨어진 주가는 5초가 된 시점이다.

6초동안의 측정 중에, 2초 시점부터 5초까지 3초 유지한다고 말할 수 있다. 

[4,3]

 

(3) 3초 시점의 주가는 3이다. 그리고 현재 주가 3 보다 떨어진 주가는 4초가 됐을 때이다.

6초동안의 측정 중에 3초 시점부터 4초까지 1초 유지한다고 말할 수 있다. 

그렇다면, 현재 인덱스 초 시점의 주가(3) 보다 떨어진 주가(2) 가 될 때까지 1초가 걸렸다. 

[4,3,1]

 

(4) 4초 시점의 주가는 2이다. 그리고 현재 주가보다 떨어진 주가는 없다.

5초동안의 측정이므로, 4초 시점부터 5초까지 1초 유지한다고 말할 수 있다.

[4,3,1,1]

 

(5) 5초 시점의 주가는 3이다. 5초 이후엔 데이터가 없기에 0초간 유지된다고 말할 수 있다.

[4,3,1,1,0]

 

접근법

- prices 배열에서 현재 주가를 기준으로 떨어진 주가가 어느 시점 인덱스인지 알아야 한다.

 

- 현재 주가 [i] 에서 앞으로의 주가들과 [i+1:] 비교해나가야 한다. 주가가 떨어졌는지 / 올랐거나 유지중인지

올랐거나 유지중이라면 1초가 지났다는 의미로 count +1 를 하고 다음 인덱스 값과 비교한다. 

떨어졌다면 1초가 지났다는 의미로 count+1를 하고 이 시점(떨어진)까지의 기간을 기록하는 것이므로 

비교를 멈추고(break) count한 이 값을 기록한다.

만약, 현 주가보다 작은 값이 없다면 6초까지의 시간 마지막 초 인덱스까지 count될 것이다.

이렇게 연산하면, 현재 주가에서 떨어진 주가까지 기간을 잴 수 있을 것이다.

 

- 본 문제는 스택/큐로 주어졌다.

리스트에서 queue구현을 위해 pop(0)을 쓴다. 그러나, 이는 pop()에 비해 O(N)으로 시간이 오래 걸린다.

그리하여, 스택과 큐를 합친 deque 자료 구조를 사용한다.

사용함수 및 적용

1. deque 사용

deque :  스택과 큐를 합친 자료구조

 

De = deque()  # deque 생성De = deque(list)  # list를 deque화 한다.De.popleft()  # 가장 왼쪽에 있는 원소를 제거하고 그 값을 리턴

 

 

소스코드

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices) # prices 원소가 있는 큐 만든다.
    while prices: # pop으로 [] 빈 큐일 때 false 빈큐가 될 때까지.
        c = prices.popleft() # 첫번째 원소 빼낸다.
        cnt = 0
        for i in prices:
            cnt += 1
            if c > i: # 빼낸 후의 큐 원소들과 하나하나 비교.
                break # 떨어진 주가 시점에서 중단.

        answer.append(cnt)

    return answer

** n + (n-1) + (n-2) + (n-3) + ... + 1 번   n(n-1)/2,   ===>  O(n^2)

 

2. list, range() 함수로

- 처음에는 enumerate()를 사용하려고 했으나,

이는 반복 자료형 내 원소를 하나씩 다 봐야하니까 O(n) 인 반면, range()는 O(1)이기에 효율성이 떨어졌기에

range()를 사용하여야 했다.

 

소스코드

# 주가가격 문제

def solution(prices):
    answer = []
    le = len(prices)
    for i in range(le):
        cnt = 0
        for j in range(i+1,le):
            cnt+=1 # 1초씩 지났다는 의미
            if prices[i]>prices[j]: # 떨어졌는지 비교
                break
        answer.append(cnt)       
    return answer
    
solution([1, 2, 3, 2, 3, 2, 1,0, 1]) # 테스트 케이스

**  O(N^2)

 

정리 

- 주식가격의 떨어짐을 비교하기 위해서는 현재 시점 이후의 원소들과 계속 비교하여야 하는데 O(N) 인 방법이 있을까나.

- Stack 으로 작성하다가 에러로 일단 포기하였는데 다른 사람 풀이에서 스택을 이용한 풀이법이 있었다. 

  다음에 한 번 더 혼자 해보고 안 되면 풀이 참고해서 시도해봐야 겠다.