스택/큐_주식가격_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)이 될 수 있음은 확실하다.

 

출처  :

programmers.co.kr/