[Python] 프로그래머스 - 스택/큐 - 주식 가격 -

목차

 

 

 

 

문제 설명

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i, len(prices)-1):
            if prices[i] <= prices[j]:
                answer[i] += 1
            else:
                break

    return answer

정확성  테스트
테스트 1 〉    통과 (0.01ms, 10.2MB)
테스트 2 〉    통과 (0.06ms, 10.3MB)
테스트 3 〉    통과 (0.76ms, 10.4MB)
테스트 4 〉    통과 (0.82ms, 10.3MB)
테스트 5 〉    통과 (1.08ms, 10.3MB)
테스트 6 〉    통과 (0.03ms, 10.3MB)
테스트 7 〉    통과 (0.46ms, 10.2MB)
테스트 8 〉    통과 (0.56ms, 10.2MB)
테스트 9 〉    통과 (0.03ms, 10.2MB)
테스트 10 〉통과 (1.12ms, 10.3MB)
효율성  테스트
테스트 1 〉    통과 (154.59ms, 18.9MB)
테스트 2 〉    통과 (119.58ms, 17.6MB)
테스트 3 〉    통과 (213.63ms, 19.4MB)
테스트 4 〉    통과 (136.61ms, 18.1MB)
테스트 5 〉    통과 (97.97ms, 16.8MB)

 

문제 풀이 과정

가격이 떨어지는 시점과 해당 가격을 모두 비교해야해서

전체적으로 값을 비교할 수 밖에 없다고 생각했다.

우선 이중 for문을 사용하면 문제 자체는 쉽게 풀 수 있을 것이라고 생각해서 문제를 풀었더니 쉽게 해결되었다.

하지만 문제의 의도인 stack/queue를 사용하지 않아서 다른 방식을 찾아보았으나,

성능적으로 크게 개선되지 않았다.

결국엔 전부 비교하는 O(n^2) 형태 같았다.

 

문제 풀면서 배운 점

다른 사람 소스 코드

def solution(prices):
    answer = [0] * len(prices)
    stack = []

    for i in range(len(prices)):
        while stack != [] and stack[-1][1] > prices[i]:
            past_idx, _ = stack.pop()
            answer[past_idx] = i - past_idx

        stack.append([i, prices[i]])

    for i, _ in stack:
        answer[i] = len(prices) - i - 1

    return answer

정확성  테스트
테스트 1 〉    통과 (0.01ms, 10.2MB)
테스트 2 〉    통과 (0.04ms, 10.1MB)
테스트 3 〉    통과 (0.50ms, 10.3MB)
테스트 4 〉    통과 (0.35ms, 10.2MB)
테스트 5 〉    통과 (0.36ms, 10.2MB)
테스트 6 〉    통과 (0.02ms, 10.1MB)
테스트 7 〉    통과 (0.19ms, 10.3MB)
테스트 8 〉    통과 (0.23ms, 10.2MB)
테스트 9 〉    통과 (0.02ms, 10.2MB)
테스트 10 〉통과 (0.37ms, 10.5MB)
효율성  테스트
테스트 1 〉    통과 (33.62ms, 18.9MB)
테스트 2 〉    통과 (25.27ms, 17.5MB)
테스트 3 〉    통과 (37.94ms, 19.5MB)
테스트 4 〉    통과 (28.90ms, 18.1MB)
테스트 5 〉    통과 (19.60ms, 16.8MB)

다른 사람의 소스코드 중 가장 잘푼 것 같은 코드를 가져왔다.

실제로 돌려본 결과 효율성 측면에서 속도가 이전 소스코드의 1/4 정도인 경우도 있을 만큼 크게 성능 향상된 것을 확인할 수 있었다.

stack에 데이터를 쌓아서 한 번에 처리하는 부분에서 시간 개선이 많이 발생된 것으로 예상된다.

많이 배웠다.

 

프로그래머스 stack & queue 다른 문제들

[Python] 프로그래머스 - 스택/큐 - 프린터

[Python] 프로그래머스 - 스택/큐 - 프린터

[Python] 프로그래머스 - 스택/큐 - 다리를 지나는 트럭 -