Programmers 스택/큐 주식가격 풀이

문제 설명

 

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

제한사항

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

입출력 예

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

 

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

나의 풀이

 

 처음 문제를 풀 때는 prices 배열에서 값을 꺼낼때 마다 이전 값들과 비교해보고 (현재값>=이전값) && (이전값이 더 적은 값이 나온적이 없는경우) 조건일 때 answer[이전값 Index] 값을 1씩 증가시키면 되겠다 생각하고 문제풀이를 시작.

 하지만 코드를 작성하고 보니, prices 배열에서 값을 하나씩 꺼낼때마다 이전 모든 값들을 스캔해야 했다. 결과적으론 실행 자체는 되었지만 효용성 테스트를 전부 통과 실패...

 해결점은 미래의 모든 값들이 prices 배열에 저장되어 있으니, 현재 값을 이전 값들과 비교해보는 것이 아니라 미래의 모든 값과 비교해 더 작은 값이 나오는 순간까지의 시간을 answer[현재값 Index]에 저장하는 점이었다. 그리고 만약 끝까지 비교해도 더 작은 값이 나오지 않는다면, 현재지점에서 배열이 끝나는 지점까지의 시간을 저장한다.

 아래는 수정 후 테스트 통과 코드

 

 

전체 코드

import java.util.*;

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++) {
                if(prices[j]<prices[i]) {
                    answer[i] = j-i;
                    break;
                }
            }
            if(answer[i]==0) {
                answer[i] = prices.length -i -1;
        }
          }
        return answer;
    }
}