문제 파악

해당 문제는 현재 인덱스의 주식 가격이 이후의 주식 가격보다 높아지는 경우가 있는지 확인하는 코드이다.

직관적으로 생각했을 때에는 중첩 반복문을 이용하여 모든 인덱스를 검사하는 완전탐색 알고리즘을 통해 문제를 해결할 수 있다.

제한사항

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

입출력 예

해당 코드에서 제한사항에는 prices의 길이가 100,000 이 될 수 있음을 암시한다.

만약, for문을 최적화하지 않는다면, 100,000 * 100,000 의 실행 횟수가 일어날 위험성이 있으므로, 최적화를 하거나, 다른 방법을 이용하여 풀이에 접근해야 한다.

접근 방법

(1) 중첩 반복문 이용 O(n^2)

간단히 각 인덱스를 늘려가며, 현재의 값 이후에 찾아지는 낮은 값이 확인된다면, 인덱스의 차이를 이용해서 얼마나 주식 가격이 유지되었는지 answer 배열에 기록한다.

이때, break문과 중첩된 내부 반복문의 인덱스를 고려하여, 최소한의 실행이 이뤄지도록 구성한다.

[pseudo code]