개요
- 문제 설명
초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
접근 방법
-
처음 문제를 보자마자 백준1725: 히스토그램문제가 떠올랐다.
-
다중반복없이 stack을 통해 뒤에서부터 훑으며 지나가면
O(n)의 시간 복잡도로 풀 수 있는 스킬이다. -
기본적인 골자는 prices벡터를 순회하며 차례대로 stack에 푸시한다.
이때, 세가지 경우가 존재한다.- stack이 empty일때
그냥 푸시한다. - stack의 top값이 현재 push하려는 값보다 클 때,
이 말은 이전 주식의 값이 하락한다는 뜻이므로, 해당 주식을 꺼내며
몇 초동안 stack에 머물렀는지 기록해야 한다. - 그 외
그냥 푸시한다.
- stack이 empty일때
-
여기에서 이제 생각해야 할 부분은 stack에서 주식을 꺼낼 때,
해당 주식이 stack에서 얼마나 머물렀는지와 초기 인덱스값을 알아야 한다. -
따라서 구조체를 만들어서 stack의 자료형으로 해당 구조체를 사용해서 관리한다.
struct stock{ int index; int price; int enteredTime; }; -
그리고 시간을 기록하기 위해선, curTime변수를 만들어서
prices벡터를 순회할때마다 증가시켜준다.
stack에 값을 집어넣을때 현재 curTime값을 푸시하고,
stack에서 값을 뺄 때, curTime-enteredTime을 하면 머물렀던 시간이 나온다.-> 사실 반복문의 index와 curTime이 동일하게 변해서 같은 숫자다.
따라서 curTime을 굳이 선언할 필요없지만 나중에 코드 봤을 때,
더 명확하게 볼 수 있게 만들어봤다for(int i=0;i<prices.size();i++){ //i와 curTime은 값이 동일하지만 나중에 이해하기 쉽게하기 위해 변수를 분리해둠 curTime++; //스택의 top price값이 현재 price값보다 크면 while(!tmpStack.empty()&& tmpStack.top().price>prices[i]){ tmpSet.insert({tmpStack.top().index, curTime-tmpStack.top().enteredTime}); tmpStack.pop(); } tmpStack.push({i,prices[i],curTime}); } -
stack에서 꺼낸 값을 정렬하기 용이하도록 set<pair<int,int>>을 하나 선언해서 first로는 초기 인덱스, second는 머물렀던 시간을 저장한다.
이렇게 저장시 set에서 초기인덱스로 정렬을 해줘서 편하다. -
{1,2,3,4,5} 이런식으로 숫자가 들어오면 모든 주식의 값이 떨어지지 않는다.
따라서 stack에 남아있는 값이 있을 수 있으므로 스택이 empty할때까지
set에 넣는 과정을 반복한다.
//반복문이 끝났는데 스택이 차있다면
while(!tmpStack.empty()){
tmpSet.insert({tmpStack.top().index,curTime-tmpStack.top().enteredTime});
tmpStack.pop();
}전체 코드
#include <string>
#include <vector>
#include <stack>
#include <set>
#include<iostream>
using namespace std;
struct stock{
int index;
int price;
int enteredTime;
};
vector<int> solution(vector<int> prices) {
vector<int> answer;
stack<stock> tmpStack;
//first는 초기 인덱스, second는 스택에 올라있던 시간
set<pair<int,int>> tmpSet;
int curTime=0;
for(int i=0;i<prices.size();i++){
//i와 curTime은 값이 동일하지만 나중에 이해하기 쉽게하기 위해 변수를 분리해둠
curTime++;
//스택의 top price값이 현재 price값보다 크면
while(!tmpStack.empty()&& tmpStack.top().price>prices[i]){
tmpSet.insert({tmpStack.top().index, curTime-tmpStack.top().enteredTime});
tmpStack.pop();
}
tmpStack.push({i,prices[i],curTime});
}
//반복문이 끝났는데 스택이 차있다면
while(!tmpStack.empty()){
tmpSet.insert({tmpStack.top().index,curTime-tmpStack.top().enteredTime});
tmpStack.pop();
}
for(auto iter=tmpSet.begin();iter!=tmpSet.end();++iter){
answer.push_back((*iter).second);
}
return answer;
}문풀후생
위에 언급했듯이 사실 curTime을 따로 선언안하고 인덱스로 다 처리를 할 수 있다.
인덱스로 처리한 코드다.
curTime을 선언하지 않고 푼 코드
#include <string>
#include <vector>
#include <stack>
#include <set>
#include<iostream>
using namespace std;
vector<int> solution(vector<int> prices) {
vector<int> answer;
//first는 초기인덱스 및 시간, second는 값
stack<pair<int,int>> tmpStack;
//first는 초기 인덱스, second는 스택에 올라있던 시간
set<pair<int,int>> tmpSet;
for(int i=0;i<prices.size();i++){
//스택의 top price값이 현재 price값보다 크면
while(!tmpStack.empty()&& tmpStack.top().second>prices[i]){
tmpSet.insert({tmpStack.top().first, i-tmpStack.top().first});
tmpStack.pop();
}
tmpStack.push({i,prices[i]});
}
//반복문이 끝났는데 스택이 차있다면
while(!tmpStack.empty()){
tmpSet.insert({tmpStack.top().first,prices.size()-1-tmpStack.top().first});
tmpStack.pop();
}
for(auto iter=tmpSet.begin();iter!=tmpSet.end();++iter){
answer.push_back((*iter).second);
}
return answer;
}