프로그래머스 - 주식가격(Level 2)/Wanna Be 컴잘알

-문제-

 

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

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

입출력 예

pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

-설명-

 

1. answer를 시작 인덱스부터 마지막 인덱스까지 가격이 떨어지지 않는다는 가정으로 초기화 시킴(왜냐면 이렇게 초기화 해줘야 prices의 마지막 인덱스까지 돌았을 때, 계속 상승하는 부분의 인덱스를 처리 안해줘도 됨 )

2. vector를 stack구조로 사용한다. => 변수 vStack

3. vStack의 top에 있는 price값이 현재 인덱스의 price값 보다 크다면(=즉, 가격이 떨어졌다면)

   answer에 인덱스 차이만큼 삽입하고 해당 vStack의 인덱스 지운다.

4. 3번을 반복한다 (조건은 top>=0, vStackp[top].price > 현재인덱스 price)

 

-코드-

#include <string>
#include <vector>
using namespace std;

void checkPrevData(pair<int,int> prices, vector <pair<int, int>> &vStack, int &top, vector<int> &answer) {
	while (1) {
		if (top == -1)
			break;

		int curValue = vStack[top].second;
		int curIndex = vStack[top].first;

		if (curValue > prices.second) {
			answer[curIndex] = prices.first - curIndex;
			vStack.erase(vStack.begin() + top);
			top -= 1;
		}
		else {
			break;
		}
	}
}

vector<int> solution(vector<int> prices) {
	vector<int> answer(prices.size());
	vector <pair<int,int>> vStack;

	int totalLength = answer.size();
	int top = -1;
	for (int index = 0; index < answer.size(); index++) {
		answer[index] = totalLength - index -1;
	}
	
	for (int index = 0; index  < prices.size(); index++) {
		if (top == -1) {
			vStack.push_back({ index,prices[index] });
			top += 1;
		}
		else {
			checkPrevData({ index, prices[index] }, vStack, top, answer);
			vStack.push_back({ index,prices[index] });
			top += 1;
		}
	}

	return answer;
}