Programmers Coding Quiz #31 주식가격(FAIL)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

풀이

def solution(prices):
    result = []
    for i, x in enumerate(prices):
        count = 0
        for y in prices[i + 1:]:
            count += 1
            if x > y:
                break
        result.append(count)
    return result

1. x를 x이후로로 부터 정렬된 리스트로 비교하면 되므로 enumerate를 통해 얻은 인덱스로 슬라이싱한 리스트를 순회하며 비교합니다.
2. count를 계속 더해주되, x가 y보다 작아진 시점에선 break로 for문을 중지하고 그 시점까지 쌓인 count를 result에 넣고, 아닌 경우 끝까지 순회에 쌓인 count를 넣어주면 됩니다.

비교적 단순하게 풀긴 했지만 결론적으로 이 풀이는 실패했습니다. 시간 복잡도에서 이중 for문은 O(N^2)의 형태를 가지게 됩니다. 다른 분들 중에 이중 for문을 쓰고도 풀어낸분이 있지만 문제의 취지에는 맞지않습니다. 이 문제는 스택과 큐를 활용해야 합니다.

(range를 활용한 이중 for문과 enumerate를 쓴 이중 for문의 차이는 enumerate는 반복자료형 원소를 하나하나 체크해야되지만, range는 그럴필요가 없이 O(1)이기 때문에 실행시간의 차이가 발생하게 됩니다.)

다른풀이

def solution(prices):
    n = len(prices)
    # 1. answer를 prices 길이와 맞춘다.
    answer = [0] * n
    # 2. 스택 생성
    st = []
    # 3. 0 ~ n-1 초까지 순회
    for i in range(n):
        # 1. 스택 비지 않고, prices[top] > prices[i] 이라면 다음 반복
        # 1-1. 스택에서 마지막에 저장된 시간 top 꺼냄
        # 1-2. answer[top]에 i - top을 저장
        while st and prices[st[-1]] > prices[i]:
            top = st.pop()
            answer[top] = i - top
        # 2. 스택에 현재 시간 i 저장
        st.append(i)
    
    # 4. 만약 스택이 남아있다면, 스택이 빌 때까지 다음 반복
    while st:
        # 1. 스택에서 마지막에 저장된 시간 top 꺼냄
        # 2. answer[top]에 가장 마지막 시간 n - i 에서 top을 뺸 시간 저장
        top = st.pop()
        answer[top] = n - 1 - top
    
    return answer

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