프로그래머스 주식가격

https://programmers.co.kr/learn/courses/30/lessons/42584

코딩테스트 연습 - 주식가격

 

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

vector<int> solution(vector<int> prices) {
	vector<int> answer;
	for (int i = 0; i < prices.size(); i++) {// 반복
		int time = 0;
		for (int j = i+1; j < prices.size(); j++) {
			++time;// 증가
			if (prices[i] >prices[j])break;
		}
		answer.push_back(time);
	}
	return answer;
}

 

위에 소스는 문제를 읽고 그냥 직관적으로 짤 수 있는 소스이다. 하지만 효율성에서 만족하지 못한다. 일일이 다 검사를 진행하기 때문이다. 그래서 N의 값이 커지게되면 시간초과가 날 수 있지만 이번 예제에서 저렇게 풀이를 해도 시간초과는 나지 않는다 하지만 그래도 최적화가 항상 중요하다. 그래서 어떻게 할지 생각해보았다. 

#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices) {
	vector<int> answer(prices.size());
	stack<int>s;
	for (int i = 0; i < prices.size(); i++) {
		while (!s.empty() && prices[s.top()] > prices[i]) {
			answer[s.top()] = i - s.top();
			s.pop();
		}
		s.push(i);//제일 위에꺼만 비교가능
	}

	while (!s.empty()) {
		answer[s.top()] = prices.size() - s.top() - 1;
		s.pop();
	}
	return answer;
}

 

두번째 소스를 보면 정말 효과적으로 시간이 개선이 된것을 볼 수 있다. stack의 특성을 이용했다. i는 일직선으로 쭉 돌게된다. push를 하면 stack의 특성상 가장 처음에 들어간것이 제일 위로 가게 된다. 탑을 쌓는것과 비슷한것이다. 

이런식으로 문제를 해결하면 좋을것 같다.