[プログラマー]-株価(スタック/キュー)

問題の説明

質問リンク
秒単位で記録された株価の配列価格をパラメータとして指定すると、価格が下がらない時間帯に数秒戻るように解く関数が完了する.

せいげんじょうけん

の価格は、それぞれ1以上10000以下の自然数です.

価格の長さは2以上100000以下です.

I/O例

pricereturn[1, 2, 3, 2, 3][4, 3, 1, 1, 0]

1秒の1はずっと値下げしていません.

2秒の2はずっと値下げしていません.

3秒の3は1秒後に値下げされます.そのため、価格は1秒以内に下がっていない.

4秒の2は1秒で値下げされませんでした.

5秒の3は0秒以内に値下げされませんでした.

問題を解く

一人で問題を理解し解決するために孤軍奮闘したが、結局他の達人の助けを受けることにした...

冗長for文の使用方法

Python

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

Java

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

Stackの利用方法

Python

def solution(prices):
    # answer = 몇초 후 가격이 떨어지는지 저장하는 배열
    answer = [len(prices)-i-1 for i in range(len(prices))]
    
    # stack = prices의 인덱스를 차례로 담아두는 배열
    stack = [0]
    
    for i in range(1, len(prices)):
        while stack:
            index = stack[-1]
            
            # 주식 가격이 떨어졌다면
            if prices[index] > prices[i]:
                answer[index] = i - index
                stack.pop()
            
            # 떨어지지 않았다면 다음 시점으로 넘어감 (주식 가격이 계속 증가하고 있다는 말)
            else:
                break
        
        # 스택에 추가한다.
        # 다음 시점으로 넘어갔을 때 다시 비교 대상이 될 예정이다.
        stack.append(i)
        
    return answer

コメントリンク

Java

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                answer[stack.peek()] = i - stack.peek();
                stack.pop();  // 답을 구했기 때문에 stack에서 제거
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) { // 값을 구하지 못한 index == 끝까지 가격이 떨어지지 않은 주식
            answer[stack.peek()] = prices.length - stack.peek() - 1;
            stack.pop();
        }

        
        return answer;
    }
}

コメントリンク