[PCCP] Lv2: 주식 가격(42584) 해설

문제

- 문제 링크: 주식 가격

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include <string>
#include <vector>

using namespace std;

// cnt++ 위치 주의!!

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    for (int i = 0; i < prices.size(); ++i){
        int cnt = 0;
        for (int j = i+1; j < prices.size(); ++j){
            cnt++;
            if (prices[i] > prices[j] || i == prices.size() - 1)
                break;
     
        }
        answer.push_back(cnt);
    }
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: prices의 길이

- 최악의 경우 각 prices의 원소들은 한 번 씩 푸시/팝하므로 시간 복잡도는 O(N)

import java.util.Stack;

class Solution {
    public static int[] solution(int[] prices) {
        int n = prices.length;
        int[] answer = new int[n]; // 가격이 떨어지지 않은 기간을 저장할 배열
        
        // 스택을 사용해 이전 가격과 현재 가격 비교
        Stack<Integer> stack = new Stack<>(); // 스택 생성
        stack.push(0);
        
        for (int i = 1; i < n; ++i) {
            while (!stack.isEmpty() && prices[i] < prices[stack.peek()]) {
                // 가격이 덜어졌으므로 이전 가격의 기간 계산
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        // 스택에 남아 있는 가격들은 가격이 떨어지지 않은 경우
        while (!stack.isEmpty()) {
            int j = stack.pop();
            answer[j] = n - 1 - j;
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: prices의 길이

- 최악의 경우 prices의 원소들은 한 번씩 푸시/팝하므로 시간복잡도: O(N)

def solution(prices):
    n = len(prices)
    answer = [0] * n # 가격이 떨어지지 않은 기간을 저장할 배열
    
    # 스택을 사용해 이전 가격과 현재 가격을 비교
    stack = [0] # 스택 초기화
    for i in range(1, n):
        while stack and prices[i] < prices[stack[-1]]:
            # 가격이 떨어졌으므로 이전 가격의 기간 계산
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    # 스택이 남아 있는 가격들은 가격이 떨어지지 않은 경우
    while stack:
        j = stack.pop()
        answer[j] = n - 1 - j
    return answer

solution 2)

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

solution 3)

import

 

(JavaScript)

solution 1)

- N: prices의 길이

- 최악의 경우 prices의 원소들은 한 번씩 푸시/팝하므로 시간복잡도: O(N)

function solution(prices) {
    const n = prices.length;
    const answer = new Array(n).fill(0); // 가격이 떨어지지 않은 기간을 저장할 배열
    
    // 스택을 사용해 이전 가격과 현재 가격을 비교
    const stack = [0];
    for (let i = 1; i < n; ++i) {
        while (stack.length > 0 && prices[i] < prices[stack[stack.length - 1]]) {
            // 가격이 떨어졌으므로 이전 가격의 기간을 계산
            const j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    
    // 스택에 남아 있는 가격들은 가격이 떨어지지 않은 경우
    while (stack.length > 0) {
        const j = stack.pop();
        answer[j] = n - 1 - j;
    }
    
    return answer;
}

solution 2)

import

solution 3)

import