ArrayStack(2)

---

stock_span

아래와 같이 n일수 만큼의 일련의 주식 시세표가 주여졌다고 가정했을 때, 특정일의 주가보다 작거나 같은 주가가 가장 길게 연속되는 날의 수를 조사하는 알고리즘이다.

ArrayStack(1)글의 헤더파일을 이용한다.

#include <iostream>
#include <vector>		//vector STL
#include "ArrayStack.h"
using namespace std;

//span을 computing하는 linear-time algorithm 함수
int computeSpans(vector<int> p) {
	ArrayStack<int> d;		//빈 stack d 선언
	int n = p.size();		//integer n에 vector의 길이 대입
	int h = 0;				//계산용 인자 h를 0으로 초기화
	int S[100];				//각 날짜의 span 값을 입력해둘 중분한 크기의 integer array S선언

	//for문을 이용하여 벡터의 사이즈n만큼 반복
	for (int i = 0; i < n; i++) {		
		int done = 0;					//done 명령어를 0으로 초기화

	//stack이 비어있거나 done명령어가 1로 바뀌지 않은 경우
		while (!(d.empty() == true or done == 1)) { 
	//stack의 top보다 조사하는 값이 더 크거나 같으면 stack에서 pop진행
			if (p[d.top()] <= p[i])		
				d.pop();
	//stack의 top보다 조사하는 값이 작으면 done을 1로 바꿔줌
			else
				done = 1;
		}
	//stack이 비어있으면 h를 -1로 설정
		if (d.empty() == true)
			h = -1;
	//이외의 경우 h를 stack d의 top으로 설정
		else
			h = d.top();

		S[i] = i - h;		//array S에 i-h를 통해 구한 span값 입력
		d.push(i);			//i값을 stack d에 push
	}

	//array S출력
	for (int i = 0; i < n; i++) {
		cout<< "Span" << i << " = " << S[i] << endl;
	};
	return 0;
}

//다양한 stock market 상황을 생성해두고 stockspan함수를 실행하는 main문
int main() {
	//다양한 stock market 상황
	vector<int> stock_value1 = { 6, 4, 1, 2, 1, 3, 5 };	//강의노트에 주어진 상황
	vector<int> stock_value2 = { 3, 2, 3, 5, 7, 8, 8, 7, 5, 3 };	//random1
	vector<int> stock_value3 = { 11, 10, 8, 6, 3, 4, 5, 4, 6, 8, 10, 12, 14 };	//random2

	cout << "Stock Span1" << endl;
	computeSpans(stock_value1);
	cout << endl << endl << endl << "Stock Span2" << endl;
	computeSpans(stock_value2);
	cout << endl << endl << endl << "Stock Span3" << endl;
	computeSpans(stock_value3);
	cout << endl << "이상훈 12211813" << endl;
	return 0;
}

배열의 크기를 integer 변수 n에 담아두기 위해 vector STL을 사용하였다. Array의 크기를 구하는 sizeof()함수를 사용하지 못한 이유는 array를 함수의 인자로 받아올 경우 array는 pointer로 인식이 되기 때문에 sizeof(array)를 하면 언제나pointer변수의 default size인 8이 출력된다. 다른 부분은 강의노트의 pseudo 코드를 기반으로 작성하였기에 특별한 내용은 없고 주석에서 모두 설명이 되었다. 다만 마지막에 각 날짜의 span값을 반복문을 이용하여 배열의 원소를 출력하여야했다.

---