[코딩테스트] 프로그래머스 : 주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

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

3초-> 4초 : 주식의 가격이 4-> 3으로 떨어진다. 즉, 1초간은 떨어지지 않았다고 볼 수 있으므로 1

4초-> 5초 : 3-> 2 => 1

 

[1, 5, 9, 3, 1] ->[4, 2, 1, 1, 0]

2초-> 4초 : 주식 가격 5-> 9-> 3, 즉, 2초간은 떨어지지 않았으므로 2

 

def solution(prices):
    answer = []
    for i, j in enumerate(prices):
        ans = 0
        for k in range(i+1, len(prices)):
            ans+=1
            if prices[k]<j:
                break
        answer.append(ans)
    return answer

이렇게 구현하면 O(n^2)

 

테스트 1 〉	통과 (96.97ms, 18.8MB)
테스트 2 〉	통과 (74.86ms, 17.4MB)
테스트 3 〉	통과 (131.79ms, 19.5MB)
테스트 4 〉	통과 (94.43ms, 18.3MB)
테스트 5 〉	통과 (58.02ms, 17.1MB)

 

 

다른 사람 풀이 : 속도가 상당히 빠르다.

스택 활용. 이렇게 하면 시간 복잡도가 O(n)이다. stack은 아직까지 단 한번도 떨어진 적이 없는 (시점, 가격)을 담고 있다.

stack을 쌓는데 n번, Stack을 해결하면서 결과를 출력하는데 다시 n번 -> 2n만큼의 계산이 진행된다. 

확실히 빠르다. 

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

테스트 1 〉	통과 (32.81ms, 18.9MB)
테스트 2 〉	통과 (26.40ms, 17.5MB)
테스트 3 〉	통과 (39.75ms, 19.5MB)
테스트 4 〉	통과 (27.86ms, 18.3MB)
테스트 5 〉	통과 (21.69ms, 16.9MB)

설명ㅇ..ㅇ stack은 단 한번도 떨어지지 않은 [index, value]를 담고 있다.