들어가는 말
주식 가격이 prices로 주어진다. 이때, 가격이 떨어지지 않는 초를 구하시오.
내가 혼자서 풀었다. 내가 혼자서 풀었다고요!!! 예~~~
앞에 들어온 prices가 먼저 나와야 하니까 큐를 쓰면 되겠다고 생각했다. 여기서 중요한 점은 뒤에 있는 prices와 비교해서 만일 언제까지 front가 작거나 같은지를 answer에 넣어주는 거다.
처음에는 time을 써서 계속 더해주다가 주식이 떨어지면 answer에 push하는 방법을 생각했다. 그러나 문제가 있었으니 만일 주식 가격이 끝까지 떨어지지 않는다면 else문에 걸리지 않아 push가 안된다는 거다. 그렇다면 for문 마지막에 push를 추가해주는 건 어떨까. 그것도 문제가 있다. for문이 마지막까지 돌아갈 때마다 push가 되는 것이다.
두 번째로 생각한 건 queue를 하나 더 만드는 거다. 현재 가격과 계속 비교해서 뒤에 있는 가격은 다른 큐에 넣어주는 거지. 근데 이건 아이디어 자체가 이상해서 패스.
세 번째로 생각한 건 트럭 문제와 같이 주식이 떨어지지 않는 시기를 0으로 표시해 큐에다가 넣고 그 사이즈를 answer에 넣어주는 방식이다. 그러나 이 방법은 첫 번째와 두 번째의 문제를 함께 가지고 있었으므로 실패.
마지막으로 쓴 게 answer의 크기를 미리 지정해두고(어차피 prices의 크기랑 같으니까) 거기다가 ++를 해주는 거다. 생각보다 편했던 게 벡터는 사이즈가 정해지면 0으로 초기화되기 때문에 굳이 마지막 값을 넣을 필요가 없다.
문제를 너무 복잡하게 풀기보다 기본으로 접근하는 게 좋을 거 같다. 넓게 보는 동시에 기본을 생각하면서. 위의 세 개의 시도는 너무 복잡하게 접근해서 문제가 됐다. 그냥 answer에 바로 더해주면 되는 것을...
코드 설명
먼저 벡터 answer의 크기를 지정해준다. answer의 크기는 prices의 크기와 동일하니 간단하다.
다음 큐의 q에다가 prices의 가격을 넣어준다.
마지막으로 while문을 돌려주는 데, current에다가 q의 front를 넣어주고 q를 pop해서 q가 빌 때까지의 조건을 충족하게 한다.
안쪽에는 for문을 돌려준다. 이때 i는 idx로 현재 current 뒤에 들어간 price를 의미한다. current와 비교해서 prices보다 작거나 같으면 answer의 idx-1에 ++해주고 아니면 ++해준 다음(가격이 떨어지더라도 current가격은 1초 유지했으니) break한다.
for문을 나오면 idx를 ++해줘서 언제나 current의 다음 price를 비교하도록 한다.
코드
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<int> solution(vector<int> prices) {
vector<int> answer(prices.size());
queue<int> q;
int current = 0;
int idx = 1;
/*필요한 변수: 큐, 시간, 하나씩 돌아야 하나?*/
for(auto pr: prices){
q.push(pr);
}
while(!q.empty()){
current = q.front();
q.pop();
for(int i = idx; i<prices.size(); i++){
if(current <= prices[i]){
answer[idx-1]++;
}else{
answer[idx-1]++;
break;
}
}
idx++;
}
return answer;
}