[프로그래머스] 주식가격 - 파이썬(python)

 

 

시간 초과된 풀이

def solution(prices):
    answer = []
    q = [(i,j) for i,j in enumerate(prices[::-1])]
    for i in range(len(q)) :
        tmp = list(filter(lambda x: x[1] < q[i][1], q[:i]))[-1:]
        if tmp == [] :
            answer.append(i)
        else :
            answer.append(i-tmp[0][0])
    return answer[::-1]

처음에는 주어진 prices 를 역순하여 (인덱스, 가격) 으로 저장하였다.

그런다음, filter 를 사용하여 해당 인덱스 보다 앞에서 더 큰 가격 중 가장 마지막 가격과의 인덱스 차이를 저장하였다.

한편, 앞에서 나보다 더 큰 가격이 없었다면 가격이 떨어지지 않았음을 의미하므로 현재 인덱스 값을 저장하도록 했다.

그러나 시간 초과로 실패하였다. filter 를 사용한 것이 문제인 것 같다.

 

 

통과한 풀이

def solution(prices):
    answer = []
    for i in range(len(prices)) :
        time = 0
        for j in range(i+1,len(prices)) :
            time += 1
            if prices[i] > prices[j] :
                answer.append(time)
                break
            elif j == len(prices)-1 :
                answer.append(time)
    answer.append(0)
    return answer

이번에는 이중 for 문을 이용해서 앞에서부터 순차적으로 풀어보았다.

i 번째와 i+1부터 끝까지를 비교하면서 더 큰 i+1 가격을 찾는다면, 걸린 시간을 추가하고, 

끝까지 찾지 못했다면 끝까지 걸린 시간을 추가하였다.

그리고 마지막 가격은 떨어지는 비교값이 없으므로 0을 추가하였다.

 

 

다른 풀이

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

내 풀이와 비슷한데, time 을 사용하지 않았다.

대신 answer list 를 0으로 초기화하고 반복문을 돌 때마다 직접 해당 위치에 1을 추가하는 방법이다.

 

 

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

큐를 이용한 풀이이다.

prices 를 큐로 만든다.

그런 다음 가장 첫번째 원소를 popleft() 로 제거하고, 남아있는 prices 와 해당 원소의 가격을 비교하며 더 작은 가격을 발견하면 반복문을 탈출한다.

 

 

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	return
[1, 2, 3, 1, 3]	[4, 2, 1, 1, 0]

stack : 주식 가격이 최초로 떨어지는 지점을 찾지 못한 (index, 가격)들의 모음 

stack 을 이용하는 이유는 다음과 같다.

stack 에 넣기전에는 항상 stack 의 top 에 있는 가격과 비교하여, 이상일 때만 넣는다.

따라서 stack 에 1 2 3 이 있었다면 다음에 삽입되는 숫자는,

3이상이므로 삽입된 것이고 이는 자연스레 모든 stack 에 있는 숫자들보다 이상의 값을 가짐을 뜻한다.

 

한편, 현재의 가격이 stack 의 top 에 있는 3보다 작은 숫자라면 pop() 을 진행하고,

또 다음으로 가장 위에 있는 값과 비교하여야 한다. 이때도 3보다 작은 숫자라면 pop() 을 진행한다.

다음으로 가장 위에 있는 값은 3보다 작지 않다면, pop() 을 멈춘다. 즉, 이제 stack 에 남아있는 숫자들은 3보다 작지 않은 값을 의미한다. -> 아직 감소하는 최초 구간을 찾지 못한 값들!

 

 

step 1 : stack에 [0,1] 추가

stack -> [0,1]

step 2 : stack 의 가장 위에 있는 가격 1보다 2가 작지 않으므로, [1,2] 도 stack 에 추가

stack -> [0,1], [1,2]

step 3 : stack 의 가장 위에 있는 가격 2보다 3이 작지 않으므로 [2,3] 도 stack 에 추가

stack -> [0,1], [1,2], [2,3]

step 4 : stack 의 가장 위에 있는 3이 1보다 크므로 [2,3] 을 stack 에서 꺼낸다.

stack -> [0,1], [1,2]

또, stack 의 가장 위에 있는 2가 1보다 크므로 [1,2] 도 stack 에서 꺼내진다.

stack -> [0,1] 

step 5 : stack의 가장 위에 있는 1보다 3이 작지 않으므로 [4,3] 도 stack 에 추가한다.

stack -> [0,1], [4,3]

 

이제 stack 에 남아있는 것들은 끝날 때까지 가격이 하락하지 않은 것들이다.

따라서 answer[i] 번에 len(prices)-1-i 의 값(끝-현재인덱스)을 저장한다.

 

 

확실히 스택을 이용한 풀이가 시간이 엄청 단축되었다!

그만큼 처음에 아이디어를 떠오르는 것이 쉽지 않다ㅠㅠ

더 많이 연습하고 익히자...!