링크

주식가격

문제설명

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

제한사항

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

입출력 예

풀이

이 문제를 처음보고 이중 FOR문으로 풀면되겠다 싶었는데 prices의 길이가 100,000이하였다. 그래서 O(N^2)을 할 시에 시간 초과가 분명 나겠다 싶어 하지않고 다른 방법을 구사해볼려고 스택과 큐도 생각해보았지만 그 부분도 O(N^2)이 뜰것 같아서 그냥 이중 FOR문으로 했는데 정답이 되어버렸다.. 왜 시간초과가 나지않을까...?

Code1

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        int[] answer = {};
        
        for(int i=0; i<prices.length-1; i++)
        {
            int num=prices[i];
            int cnt=0;
            for(int j=i+1; j<prices.length; j++)
            {
                if(num <= prices[j])
                    cnt++;
                    
                if(num > prices[j]) 
                {
                    list.add(++cnt);   
                    break;
                }
                
                if(j==prices.length-1)
                {
                    list.add(cnt);
                    break;
                }
            }   
            
        }
        
        list.add(0);
        answer=new int[list.size()];
        
        for(int i=0; i<list.size(); i++)
            answer[i]=list.get(i);
        return answer;
    }
}

Code2

간결하게 구현

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        for(int i=0; i<prices.length; i++)
        {
            for(int j=i+1; j<prices.length; j++)
            {
                answer[i]++;
                if(prices[i] > prices[j])
                    break;
            }
        }
        return answer;
    }
}