프로그래머스 - 주식가격(Java, LV2)

https://programmers.co.kr/learn/courses/30/lessons/42584?language=java

코딩테스트 연습 - 주식가격

 

prices의 해당 값이 떨어졌을 때 

그 시점의 인덱스 차이를 넣어주면 된다.

단, 값이 떨어질 경우없이 끝까지 갔을 경우에는 -1을 해줘야함(끝까지 간 경우는 index를 1 초과했으므로)

그리고 마지막 값은 무조건 0 이므로 계산해주지 않아도 된다.

 

아무리 생각해도 O(n^2)을 극복하는 방안이 안떠올랐다...

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        
        int[] answer = new int[prices.length];
        
        for(int i=0; i<(prices.length -1); i++){

            // i 보다 클동안 증가
            for(int j=i+1; j<=prices.length;j++){
                // 끝까지 갔을 경우 -1 해줘야함(인덱스 차이)
                if(j == prices.length)
                    answer[i] = j-i-1;
                
                // 인덱스 차이 값 삽입
                else if (prices[i] > prices[j]){
                    answer[i]=j-i;
                    break;
                }
            }
        }
    
        
        return answer;
    }
}