[자료구조론] Stock Span Problem 주가 스팬 구현(Linear/Quadratic-Time)

Stock Span problem 이란?

https://thebook.io/006952/ch01-01/

리얼월드 알고리즘: 1장 주가 스팬 - 1

배열이 주어졌을 때, 각각의 인덱스에서 해당하는 값과 앞의 인덱스와 연쇄적으로 비교한다. 

이때 자신을 포함한 앞의 인덱스의 값들 중에서 자신의 값과 작거나 같은 인덱스의 개수를 스팬이라고 정의한다.

 

Stock Span Problem 을 해결하는 코드는 두 가지 종류가 있는데, 

 

Quadratic-Time Algorithm

O(n^2)의 Big Oh Notation을 가지는 알고리즘이다.

 

#include <iostream>
using namespace std;

int main() {
	int arr[7] = { 1,1,1,2,1,4,6 };
	int ans[7] = {};
	for (int i = 0; i < 7; i++)
	{
		int k = 0;
		for (int j = i - 1; j >= 0; j--) {
			if (arr[i] >=  arr[j]) {
				k++;
			} 
			else {
				break;
			}
		}
		ans[i] = k;
	}
	cout << endl;
	for (int i = 0; i < 7; i++) {
		cout << ans[i] << " ";
	}
}

#include <iostream>
using namespace std;

int main() {
	int arr[7] = { 1,1,1,2,1,4,6 };
	int ans[7] = {};
	for (int i = 0; i < 7; i++) {
		int k = 1;
		while (i - k > 0) {
			if (arr[i - k] <= arr[i])
				k++;
			else
				break; // SPAN_END = TRUE
		}
		ans[i] = k;
	}

	cout << endl;
	for (int i = 0; i < 7; i++) {
		cout << ans[i] << " ";
	}
}

각 배열의 인덱스 값(i)를 기본으로, 위의 코드는 for문으로, 밑의 코드는 while문으로 구현하였다. 

 

근데 두 코드 출력이 다름,, 

아마 while문으로 짠 밑에 코드가 틀린 것 같은데 어디서 버그를 해결해야 할지 감을 못 잡겠다. 😥

 

그 다음은 Linear Time Algorithm !!

스택을 이용해서 Linear-time 에 문제를 해결한다. 

특정 인덱스의 주가보다 큰 주가를 가지고 있는 날(인덱스)을 알고 있다면, 

이를 따로 저장해서 특정 인덱스에 대한 스팬을 구할 수 있다.

 

h(i) : i로부터 선행하는 날이 존재할 경우, 해당 날을 의미 (존재하지 않는다면 -1로 초기화)

이에 의해, 첫째 날의 스팬은 si = i - h(i)로 계산된다. 

 

스택에서 해당 인덱스의 Pi보다 작거나 같은 날은 pop하고, i를 push한다. 

 

 

 다음과 같은 주식 그래프가 있다고 할 때, 

 

Linear Time Algorithm은 다음과 같다.

1) 0부터 6까지 변수 i가 순회

2) 처음에는 D가 Empty 상태이므로 따로 비교하지 않고, h = -1 대입 후 0을 D에 push한다.

3) 그 이후부터는 자신과 스택에 쌓여있는 날들 중 가장 최근에 넣어진 날들과 주식 값을 비교, 자신이 더 크거나 같다면 방금 비교한 주식 값을 D에서 pop하고, 그 다음에 들어있는 스택의 값과 비교해 자신이 더 '작을 때'까지 반복한다.

4) 그리고 S라는 배열에 i - h를 한 값을 계속 넣어준다. i - h는 스팬의 개수를 세는 공식으로, 현재의 위치에서 싸움에서 최초로 진 날의 위치를 뺀 것을 의미한다. 

 

D 스택은 '승자 리스트'라고 알면 될 것 같구

제일 마지막 턴에서 살아남은 두 개의 스택 요소 중에서 아래에 위치한 것이 가장 주식 값이 큰 날에 해당한다.

(제일 위의 값은 싸우지 않고 남아있는 제일 마지막 값)

 

위 그래프에 따르면

S의 배열은

1 1 1 2 1 4 6

이 되는 것이 정상이다. 

 

위에 내가 짠 코드랑 좀 다른데?

이렇게 다양한 경우에서 알고리즘의 진행도를 그려보자. 

 

 

#include <iostream>
using namespace std;
#include "Stack.h"
#include <vector>

int main() {
	Stack D;
	int h;
	int arr[7] = { 9,5,2,3,1,4,7 };
	int ans[7];
	try {
		for (int i = 0; i < 7; i++) {
			while (!D.empty()) {
				if (arr[D.top()] <= arr[i])
					D.pop();
				else
					break;
			}
			if (D.empty())
				h = -1;
			else
				h = D.top();
			ans[i] = i - h;
			D.push(i);
		}
	}
	catch (const IndexOutOfBounds& e) {
		cout << "Error occured : " << e.get_message() << endl;
	}
	for (int i = 0; i < 7; i++) {
		cout << ans[i] << " ";
	}
}

 

위의 알고리즘을 코드로 구현한 것,

이때는 empty() 호출 시 스택이 비어있는 경우를 방지하기 위해 try catch문을 작성하였다. 

 

이렇게 스톡 스팬 알고리즘 구현 완료!