[백준] 11501번 - 주식 (C++)

문제

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

---

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

---

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

---

 

예제 입력 1 복사

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

예제 출력 1 복사

0
10
5

 

---

풀이과정

#include <iostream>
#include <algorithm>
#include <vector>

int		main(void)
{
	int t, n, temp, max, m;
	std::vector <int> v;

	std::cin >> t;
	for(int i = 0; i < t; i++)
	{
		std::cin >> n;
		for(int j = 0; j < n; j++) {
			std::cin >> temp;
			v.push_back(temp);
		}
		m = 0;
		for (int k = 0; k < v.size(); k++) {
			max = 0;
			for(int j = k; j < v.size(); j++) {
				if (max < v[j]) max = v[j];
			}
			if (v[k] < max) m += max - v[k];
		}
		std::cout << m << "\n";
		v.clear();
	}

	return (0);
}

문제에서 시간제한이 5초로 주어졌길래 엄청 넉넉하다라고 생각했었는데 

2중 for문 방식으로 n만큼을 2번도니 O(N^2)의 시간이 되어 시간초과가 발생이 되었던 거 같다.

이후로 코드는 그대로 두고 시간을 어떻게 줄일 수 있을지 고민을 하다가 2중 for문 부분에서 현재 검사하는 (v[k]) 값 이후로 가장 큰 값을 찾는 저 파트를 algorithm 매소드에 내장이되어있는 가장 큰 값을 바꾸는 함수로 바꾸면 시간초과가 발생하지 않지않을까라는 생각을 가지고

#include <iostream>
#include <algorithm>
#include <vector>

int		main(void)
{
	int t, n, temp, max;
	long long m;
	std::vector <long long> v;

	std::cin >> t;
	for(int i = 0; i < t; i++)
	{
		std::cin >> n;
		for(int j = 0; j < n; j++) {
			std::cin >> temp;
			v.push_back(temp);
		}
		m = 0;
		for (int k = 0; k < v.size(); k++) {
			max = *std::max_element(v.begin() + k, v.end());
			if (v[k] < max) m += max - v[k];
		}
		std::cout << m << "\n";
		v.clear();
	}

	return (0);
}

max_element 함수를 써가면서 사용을 해봤는데

결과는 똑같이 시간초과가 발생이 되었다. 곰곰이 생각을 해보니 max_element라는 함수자체도 내부에서는

내가 구현한 vector를 돌아서 큰값을 찾는 것과 로직이 크게 다르지는 않을거 같다는 생각이 들어서 시간복잡도에는 차이가 생기지 않는다고 생각을 가지게 되었고, 저 문제를 풀기위해서는 O(N^2) 형식은 불가능하고 O(N)이어야만 풀 수 있겠다라는 생각이 들어서 2중 for문을 제거하기위해서 새롭게 로직을 생각하게 되었다. 고민을 하다가 나온 로직이 아래에 나와있는 이 로직이다.

#include <iostream>
#include <algorithm>
#include <vector>

int		main(void)
{
	int t, n;
	long long m, temp, max;
	std::vector <long long> v;

	std::cin >> t;
	for(int i = 0; i < t; i++)
	{
		std::cin >> n;
		for(int j = 0; j < n; j++) {
			std::cin >> temp;
			v.push_back(temp);
		}
		m = 0;
		max = 0;
		for (int k = v.size() - 1; k >= 0; k--) {
			if (v[k] > max) max = v[k];
			else if (v[k] < max) m += max - v[k];
		}
		std::cout << m << "\n";
		v.clear();
	}

	return (0);
}

이 로직은 2중 for문 대신 배열을 역순으로 돌아서 큰 값(max)를 갱신해가며 진행이 되고 큰 값(max) 이후로 나오는 작은 값은 주식이 올랐다는 말과 같은 의미가 되므로 max(큰값) - v[k](현재 검사중인 값)으로 주식수익의 총합으로 더해주었다.

이런식으로 시간복잡도를 O(N^2)에서 O(N) 형식으로 바꾸게되니 문제를 해결 할 수 있었다.

code

#include <iostream>
#include <algorithm>
#include <vector>

int		main(void)
{
	int t, n;
	long long m, temp, max;
	std::vector <long long> v;

	std::cin >> t;
	for(int i = 0; i < t; i++)
	{
		std::cin >> n;
		for(int j = 0; j < n; j++) {
			std::cin >> temp;
			v.push_back(temp);
		}
		m = 0;
		max = 0;
		for (int k = v.size() - 1; k >= 0; k--) {
			if (v[k] > max) max = v[k];
			else if (v[k] < max) m += max - v[k];
		}
		std::cout << m << "\n";
		v.clear();
	}

	return (0);
}

---

후기

시간복잡도를 미리 계산을 해보고 설계를 제대로 세워서 문제에 접근을 했으면 시간초과를 저렇게 많이 내지않고 빠르게 문제에 접근 할 수 있었을 거 같은데 아직 시간복잡도를 계산하는것도 설계하는 부분에 있어서 많이 부족하다고 느끼게 되었다.

더욱 다양한 문제들의 접근을 해봐서 빠르게 효율적인 로직을 설계할 수 있도록 노력을 해야할 거 같다.