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

문제

• 가격이 떨어지지 않은 기간이 몇 초인지 리턴하기
• 초 단위로 기록된 주식가격이 prices 이다.
  • 2 <= prices 길이 <= 100,000

 

풀이

• 완전 탐색
• 하나씩 살펴보면서 가격이 언제 떨어지는지 카운팅하기
• 시간 복잡도 : $O(N^2)$ 안됨
  
  • 효율성 통과하는 것 보면 최악의 케이스가 없는 것 같다..

 

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

 

References

• 프로그래머스 고득점Kit 스택/큐