1.문제
2. 접근/체크포인트
- prices의 각 가격은 무조건 1 이상
- 현재 시점(index)이후로 마지막 시점(index)까지 지금 시점의 가격보다 낮아지는 시점이 있는지 확인
3. 해결 방법
- int형 stack s에 prices의 index를 넣어서 현재 시점(index) 이후의 값들과 비교한다.
- 만약 prices[s.top()]이 prices[i]보다 클 경우는 가격이 떨어진 시점이 존재하는 것으로 총 시간에서 이를 제외한 값을 answer에 추가한다. 답 계산 후 스택의 최상단 원소(인덱스)는 제거하고 새로운 인덱스를 추가하여 다시 비교한다.
- 그 외의 경우는 가격이 떨어지지 않은 경우이므로 가격이 떨어지지 않은 경우이므로 스택에서 하나씩 원소(index)를 제거해가며 해당 index의 정답을 입력한다.
4.전체코드
#include <string>
#include <vector>
#include<stack>
using namespace std;
vector<int> solution(vector<int> prices) {
// answer 벡터를 prices의 크기만큼 0으로 초기화함.
vector<int> answer(prices.size());
//pricse의 idx를 push 할 stack
stack<int> s;
//첫 번째 idx(0) 넣고 시작
s.push(0);
for(int i=1; i<prices.size(); i++){
//1. 가격이 떨어진 경우
while( !s.empty() && prices[s.top()]>prices[i]){
answer[s.top()] = i-s.top();
s.pop();
}
//다음 idx push
s.push(i);
}
//2. 가격이 안 떨어진 경우
while(!s.empty()){
answer[s.top()] = prices.size()-1-s.top();
s.pop();
}
return answer;
}
5. 참고사항
👉 C++의 vector 초기화 방법
#include <vector> // vector가 들어있는 헤더파일 vector<int> v; // int타입 벡터 생성 (초기화X) vector<int> v = { 1, 2, 3}; // int형 백터 생성 후 1, 2, 3 으로 초기화 vector<int> v[10]; // int타입 벡터 배열(크기 : 10) 생성 vector<int> v(5); // 5개의 원소를 0으로 초기화
- 마지막 방식을 이용하여 주어진 prices배열의 크기로 answer벡터를 생성하고 0으로 초기화하여 이용.
6.다른 방법으로 풀어보기
추후 추가 예정
7. 후기
처음에는 현재 인덱스랑 그 이후 인덱스를 전부 비교해서 시간을 계산하는 간단한 문제인데, 왜 문제 카테고리가 스택/큐인지 잘 이해를 못했다. 역시나 전부 비교하는 방식으로 할 경우 시간 초과로 효율성 테스트를 하나도 통과할 수 없었고, 스택을 이용하는 방식으로 풀이하였다. 이 방식도 처음에 스택에 prices의 원소가 아닌 index를 대입한다는 발상이 잘 떠오르지 않아 오래걸렸고, 그 이후 시간을 계산하기 위해 변수간의 관계식을 찾는 것도 쉽지 않았다. 사실 문제도 처음부터 100% 이해한건 아니였,,, 나중에 다시 풀어보고 다른 사람들의 풀이도 참고해서 내용을 업데이트할 예정!
Frontend-Devloper