[프로그래머스] 주식가격(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "주식 가격" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 효율적인 데이터 구조와 알고리즘을 사용하여 주식 가격의 변동을 분석하는 데에 중점을 둡니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=cpp

프로그래머스

문제 개요

"주식 가격" 문제에서는 초 단위로 기록된 주식 가격 배열이 주어지며, 각 가격이 떨어지지 않은 기간을 초 단위로 계산하여 반환하는 것이 목표입니다. 이 문제는 효율적인 데이터 구조와 알고리즘을 사용하여 주식 가격의 변동을 분석하는 데에 중점을 둡니다.

해결 방법

이 문제를 해결하기 위해선 각 가격이 떨어지지 않는 시간을 효과적으로 계산할 수 있는 알고리즘을 구현해야 합니다. 이를 위해 큐(queue)를 사용하여 각 가격을 순차적으로 처리하고, 가격이 떨어질 때까지의 시간을 계산합니다.

코드 구현

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    queue<int> q;

    // 주식 가격들을 큐에 삽입
    for(int i = 0; i < prices.size(); i++){
        q.push(prices[i]);
    }

    // 큐에 남아있는 주식 가격을 차례대로 처리
    while(q.size()){
        for(int i = 0; i < prices.size(); i++){
            int temp = q.front(); // 현재 가격
            q.pop(); // 큐에서 제거
            int sum = 0; // 가격이 떨어지지 않은 시간
            // 현재 가격 이후의 가격들을 확인
            if(i + 1 < prices.size()){
                for(int j = i + 1; j < prices.size(); j++)
                {
                    sum++;
                    if(temp > prices[j]) break; // 가격이 떨어진 경우 루프 종료
                }          
            }
            answer.push_back(sum); // 결과에 추가
        }
    }

    return answer;
}

코드 설명

이 코드는 주식 가격 배열 prices를 입력으로 받아, 각 가격이 떨어지지 않은 기간을 초 단위로 계산하여 반환합니다. 주식 가격은 큐에 저장되어 순차적으로 처리됩니다. 각 가격에 대해, 해당 가격 이후의 모든 가격을 순회하면서 가격이 떨어질 때까지의 시간을 계산합니다. 이 시간은 answer 벡터에 추가되어 최종적으로 반환됩니다.

결론

"주식 가격" 문제는 큐를 활용한 시간복잡도 효율적인 방법으로 해결할 수 있습니다. 각 주식 가격에 대해 가격이 떨어지지 않은 기간을 계산하고, 이를 순차적으로 분석하여 문제의 요구사항을 만족시키는 결과를 도출합니다. 이러한 접근 방식은 다른 시계열 데이터 분석 문제에도 적용될 수 있습니다.