[C++] 주식 가격

링크

---

https://programmers.co.kr/learn/courses/30/lessons/42584#

코딩테스트 연습 - 주식가격 | 프로그래머스

 

 

문제 설명

---

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

 

 

제한 조건

---

 

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

 

 

 

입출력 예

---

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

 

 

풀이

---

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
    int priceSize = prices.size();
    vector<int> answer(priceSize);
    answer[priceSize - 1] = 0;
    
    for(int i = priceSize - 2; i >= 0; --i)
    {
        int currPrice = prices[i];
        if(currPrice > prices[i+1])
        {
            answer[i] = 1;
            continue;
        }
        
        int checkIndex = answer[i+1] + 1 + i;
        while(checkIndex < (priceSize-1) && currPrice <= prices[checkIndex])
        {
            checkIndex += answer[checkIndex];
        }
        answer[i] = checkIndex - i;
    }
  
    return answer;
}

 

 

풀이 설명

---

 문제를 읽어봤을 때 vector를 순회하면서 하나하나 값 비교를 통해 정답을 도출할 수 있지만 효율이 좋지 않다.

그래서 다음과 같은 로직으로 풀었다.

 

일단 vector를 거꾸로 순회하였다. 왜냐하면 과거의 결과를 통해 현재의 결과를 구하기 위해서!

 

일단, answer의 마지막 인덱스 값(answer[4])은 무조건 0이다.

 

다음에, answer[3]의 값을 구해야 한다.

 

1. prices[3]은 2고, prices[4]는 3이다.

 

2. 그 말은 즉슨, 2는 3보다 작은 값이고 가격이 언제 떨어졌는지 조사하기 위해선 prices[4]가 언제 가격이 떨어졌나

조사할 필요가 있다.

 

3. answer[4]를 통해 prices[4]가 언제 가격이 떨어졌나 조사를 해본다.

 

4. answer[4]를 봤더니 값이 0이다.(마지막 인덱스라는 뜻)

 

5. 즉 prices [3]은 마지막까지 가격이 안 떨어졌다는 의미이므로 answer[3] = 마지막 인덱스 - 현재 인덱스 = 1이다.

 

 

다음의 경우는 매우 간단하다 3은 2보다 값이 크므로 가격이 바로 떨어진다고 볼 수 있다.

즉 answer[2] = 1이다.

 

 

 

 

 

 

설명이 길어서 되게 어렵고 거창해 보이는데 간단하다.

내 앞의 녀석이 언제 가격이 떨어졌는지 앞의 answer를 통해 참고하여 내 answer를 구한다.

 

이게 끝이다.