[스택/큐] 주식가격

|| 문제설명 ||

1. 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어진다.

2. 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하여라.

_ 1 <= (prices의 각 가격) && (prices의 각 가격) <= 10,000, 자연수
_ 2 <= (prices의 길이) && (prices의 길이) <= 100,000

---

|| 문제해결과정 ||

- cnt : 해당 가격이 떨어지지 않은 기간
- for문 2개를 이용
	바깥쪽 for문 범위(i) : prices.begin() ~ prices.end()-1
    	안 쪽 for문 범위(j) : i+1 ~ prices.end()
- 바깥쪽 for문을 기준으로 안쪽 for문을 이용하여 현재 값이 다음 값보다 작거나 같으면 cnt를 증가
- 마지막에 추가로 answer에 0 푸시

---

|| 코드 ||

[2020.08.02] 실패

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) {
  vector<int> answer;
  int cnt = 0;
  for(auto i = prices.begin(); i != prices.end() - 1; i++) {
    for (auto j = i+1; j != prices.end(); j++) {
      if (*i <= *j) cnt++;
    }
    answer.push_back(cnt);
    cnt = 0;
  }
  answer.push_back(0);
  return answer;
}

[ 실행과정 ]

[ 문제발견 ]

• 예외처리 : i = 3(prices[2])일때,가격이 떨어지는 순간 멈춰야하는데 다음을 진행하므로 멈춰줘야함.
• 문제이해 부족 : 다음 가격으로 넘어가는 사이에 1초가 흐른다. (i=3일때 0이 아닌 1이 나오는 이유) → 가격이 떨어져 멈추더라도 1초는 지나가있다.

[2020.08.02] 성공

- else 문을 추가하여 
	가격이 떨어질때 cnt를 증가시키고 멈춰준다.

#include <string>
#include <vector>


using namespace std;

vector<int> solution(vector<int> prices) {
  vector<int> answer;
  int cnt = 0;
  for(auto i = prices.begin(); i != prices.end(); i++) {
     for (auto j = i+1; j != prices.end(); j++) {
        if (*i <= *j) cnt++;
        else {
            cnt++;
            break;
        }
     }
     answer.push_back(cnt);
     cnt = 0;
  }
  return answer;
}

실행과정 >>

---

[2020.08.02] 도전중

- for문을 하나만 쓰기 

#include <string>
#include <vector>


using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size()), tmp;
    int cnt = 0, pre = prices[prices.size()-1], chk[100005] = {0};
    
    chk[pre]++;
    answer[prices.size()-1] = 0;
    
    for(int i = prices.size()-2; i >= 0; i--) {
        if(prices[i] <= pre ) { cnt++; }
        else { cnt = 0; }
      
        cnt += chk[prices[i]];
        chk[prices[i]] = cnt; 
        pre = prices[i];    
        answer[i] = cnt;
    }
    return answer;
}

---

[2021.01.15]

- o(n^2)

#include <string>
#include <vector>

using namespace std;

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