프로그래머스_주식가격 (java)

 

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

 

제한사항:

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

1. 처음 푼 방법 - 이중 for문 돌면서 지정한 i인덱스의 값과 j인덱스의 값을 비교해 i인덱스의 값보다 떨어질때까지 answer배열 i 인덱스 값을 ++해줌.

 

(자바)

public static int[] solution(int[] prices) {
    int len = prices.length;
    answer = new int[len]; // answer배열도 prices크기만큼

    int i, j; 
    for (i = 0; i < len; i++) {
      for (j = i + 1; j < len; j++) { // i이후에 떨어질 때 만 비교함으로 j = i+1
      answer[i]++;
        if (prices[i] > prices[j]) // 가격이 떨어지면 break로 innerloop빠져나가고 i값 증가
        	break;
      }
    }
    return answer;
}

 

(파이썬)

def solution(prices):
    answer = [0] * len(prices)
    
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]:
                break
    return answer

 

2. 두 번째 방법 - 시간복잡도를 줄이기 위해 스택에 인덱스값을 넣어 prices[i]와 prices[stack.peek()]을 비교하면서 값이 떨어지는지를 판별

 

㉠ 처음 인덱스는 무조건 스택에 넣고 그 뒤로는 prices[i]와 prices[stack.peek()]을 비교하면서 증가할 동안 push

㉡ 위 처럼 반복하다가 비교값이 떨어지면 인덱스의 차이( = 주식가격이 떨어지지 않은 시간)를 stack.pop값과 같은 answer배열 인덱스에 넣음.

 

㉢ 비교하고 남은 stack의 값 처리 : 전체 배열길이-1(=prices배열 인덱스끝값)에서 각 stack값들을 빼면 각각의 차이가 나옴. 똑같이 answer배열에 차이값을 담음.

☆사진에는 배열전체길이라고 적어놨는데 (prices배열길이 - 1) - stack.pop() 이 맞다(인덱스끝값을 가져와야함으로)

 

소스코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        // 각 가격마다 떨어지지 않은 시간을 return 함으로 prices배열크기만큼 answer배열 지정
        int[] answer = new int[prices.length]; 
        
        Stack<Integer> stack = new Stack<Integer>(); // 인덱스 값을 넣을 스택생성
      
        for(int i=0; i<prices.length; i++) {
            while(!stack.empty()) { // 스택이 안비었을 때
                if(prices[stack.peek()] > prices[i]) { // 스택peek인덱스 값보다 i인덱스의 값이 작을 때 , 즉 값이 떨어졌을 때
                    int preEl = stack.pop(); 
                    answer[preEl] = i-preEl; // 떨어진 시점의 인덱스 - 스택 상단값(이전 인덱스) 차이
                } else {
                    break;
                }
            }
            stack.push(i); // 스택이 비었거나, 값이 같거나 증가할 때
        }
        
        while(!stack.empty()) { // 남은 스택 처리
            answer[stack.peek()] = (prices.length-1) - stack.pop(); // 인덱스끝에서 스택에 담긴 인덱스들의 차이
        }
        return answer;
    }
}