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

주식가격

문제설명

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

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

문제 분류가 스택/큐 이지만...어이없게도 스택/큐를 썼더니 정답은 맞고 효율성 테스트에서 0점을 받았다.
분명 시간 복잡도가 O(n^2)가 나올 것 같아 가격이 낮은 인덱스를 볼 때마다
맨 앞에 껄 pop 하면 리스트 길이도 작아지니까 괜찮겠지..라는 생각이었다.

30분정도 고민하다가
그냥 이중for문을 사용했더니 풀렸다.
첫번째 for문에서 prices의 길이만큼 돌리고
두번째 for문에서 첫번째 for문의 인덱스부터 뒤까지 쭉 비교하는 코드이다.
테스트 케이스의 실행 속도도 둘 다 차이는 없는거 같은데..
왜 첫번째 코드가 틀린지는 모르겠다..

코드

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