[level 2] 주식 가격

1. 문제

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

 

제한사항

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

 

---

2. 문제 풀이 

1) queue에 원소가 있을 동안 반복한다

2) queue에서 가장 첫번째 원소를 pop한다.

3) 만약 queue에 원소가 있다면, 큐에 남아 있는 원소를 탐색하며 현재 주식 가격이 해당 시점 가격보다 높거나 같은지 확인한다. 만약 같다면 count+1을한다.

4) 만약 떨어졌다면 1초 동안 가격을 유지한 것이므로 count+1을 하고 break를 해서 나온다

5) answer에 count 값을 추가한다. 

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

 

효율성 테스트 진짜 간당간당하게 통과함..

아무래도. 시간 복잡도 거의 O(N^2) 일 것 같은데 

 

---

3. 다른 사람들 문제 풀이

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

 

prices의 가격 만큼 for문을 진행한다. 

만약 스택이 비어 있지 않다면, 그리고 스택의 첫번째에 있는 가격이 i번째(현재) prices보다 크다면 원소를 빼낸다.

(이때, 인덱스만 추출함)

현재 인덱스 i와 제거된 past 인덱스의 차이를 answer[past]에 저장한다

(인덱스 차이 = 유지된 시간) 

 

스택에 아직 원소가 남아 있는 경우, 즉 가격이 떨어지지 않은 경우에는 

남아 있는 각 요소에 대해 answer[i]를 현재 인덱스에서 마지막 인덱스까지의 차이로 정한다. 

 

 

...이런 생각은 대체 어떻게 하는 거지 진짜

스택/큐 문제 백준에서 더 풀어봐야겠다.