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

문제

 

 

풀이 #1(이중 반복문 - O(n^2))

def solution(prices):
    res = []
    last_index = len(prices) - 1
    
    #첫 인덱스부터 반복하며 비교
    for i in range(len(prices)) :
    	#마지막 인덱스일 경우, 0 추가
        if i == last_index : 
            res.append(0)
            break
        #현재 비교하는 인덱스부터 끝까지 비교
        for j in range(i + 1, len(prices)) :
            if prices[i] > prices[j] :
                res.append(j - i)
                break
            #비교하다가 마지막 인덱스에 오면 (마지막 인덱스 - 현재 인덱스) 추가
            elif j == last_index :
                res.append(last_index - i)
    
    return res

 

문제를 봤을 때는, 떠올랐던게 이중 반복문이어서 일단 코드를 짜고 정답까지는 맞았는데, 이중 반복문을 사용하다보니 prices 리스트가 길 경우에 시간이 기하급수적으로 늘어날 것 같다고 생각했다..

 

풀이 로직 #1

1. 첫 인덱스부터 ~ 끝 인덱스까지 반복

2. 현재 비교하는 인덱스부터 끝까지 비교하여, 처음 가격이 낮아지는 인덱스에서 현재 인덱스를 뺀 값을 append

3. 비교하다가, 마지막 인덱스와 비교할 시에(끝까지 떨어지지 않음) 마지막 인덱스 - 현재 인덱스 값을 res에 추가

4. i가 마지막 인덱스 일경우(리스트의 마지막 원소의 떨어지지 않은 기간은 무조건 0) 0 반환

 

풀이 #2 (Stack 사용 - O(n))

def solution(prices):
    n = len(prices)
    res = [0] * n	#prices의 길이만큼 0을 저장한 리스트
    stack = []  # 인덱스를 저장

    for i in range(n):
        # 현재 가격이 스택 top의 가격보다 낮으면 가격이 떨어진 시점
        while stack and prices[stack[-1]] > prices[i]:
            past_idx = stack.pop()
            res[past_idx] = i - past_idx  # 버틴 시간
        stack.append(i)

    # 스택에 남은 건 끝까지 가격이 안 떨어진 경우
    while stack:
        past_idx = stack.pop()
        res[past_idx] = n - 1 - past_idx

    return res

 

 

풀이 로직  #2

1. i는 현재 인덱스, 반복

2. 현재 가격(prices[i])이 스택의 top의 가겨보다 낮으면 pop 후 버틴 시간 기록(현재 시간 : i이므로 들어간 index를 빼면 됨)

-> past_index : 과거 저장된 인덱스값

3. 낮지 않으면 현재 인덱스 push

4. 끝까지 안떨어진 경우 : stack에 남아있으므로 len(prices)에서 뺄셈하여 res의 해당 index에 추가

 

 

 

Github Link    ←