[프로그래머스] 주식가격 (C++)
📌 참고
교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers
코딩테스트 고득점 Kit > 스택/큐
문제풀이 (2022-01-20 WED 💻)
🤔 사담 + ⭐ 풀이의 핵심?!
스택/큐 유형으로 분류되어 있는 문제라서
스택을 활용해서 풀어보려고 머리를 굴렸는데 잘 떠오르지 않았다
그래서 그냥 그대로 구현하는 느낌으로 이중 for문 써서 돌려봤는데
O(N^2) 복잡도라 걱정했는데.. 다행히 시간초과는 안 떴다 (?)
cf) 진짜 신기하게도 이중 for문 쓴 코드랑 stack 쓴 코드랑 효율성이 비슷하게 나타났다
특별히 떠오르는 방법이 없다면 직관적으로 푸는 것도 나쁜 것만은 아닌듯!🔽 이중 for문 코드 효율성 테스트 결과
🔽 stack 코드 효율성 테스트 결과
오늘 내 풀이는 너무 직관적이라 설명할 게 딱히 없다
👇 스택으로 푸는 방법이 궁금해서 구글링 후 코드를 수정해보았다
✅ 구글링을 통해 얻은 Tip
prices 배열 값, 즉 주식가격을 스택에 넣어보려고 했었는데
prices 배열 인덱스, 즉 해당 주식가격의 시점(초 단위) 을 스택에 넣는 게 핵심이었다
👉 prices 배열을 돌면서
i) 가격이 떨어지지 않은 경우 스택(timeStack)에 시점을 push하고
ii) 가격이 떨어진 경우 현재 시점(i) - 해당 시점(timeStack.top())의 값을
answer 벡터의 해당 시점 인덱스에 저장해주고 해당 시점을 pop해준다
👉 prices 배열을 다 돌았는데 스택(timeStack)이 비어있지 않은 경우에는
끝까지 가격이 떨어지지 않은 해당 시점들이 있다는 뜻이므로 스택이 빌 때까지
마지막 시점(prices.size() - 1)에서 해당 시점(timeStack.top())을 빼준 값을
answer 벡터의 해당 시점 인덱스에 저장해주고 pop해준다
🔽 이중 for문을 활용한 코드 (C++)
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> prices) {
int N = prices.size();
vector<int> answer(N, 0);
for (int i=0; i<N; i++) {
for (int j=i+1; j<N; j++) {
answer[i]++;
if (prices[i] > prices[j]) { break; }
}
}
return answer;
}
🔽 stack을 활용한 코드 (C++)
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices) {
int N = prices.size();
vector<int> answer(N);
stack<int> timeStack;
for (int i=0; i<N; i++) {
while (!timeStack.empty() && prices[i] < prices[timeStack.top()]) { // 가격이 떨어진 경우
answer[timeStack.top()] = i-timeStack.top(); // 떨어지지 않은 기간 계산 (현재 시점 - 해당 시점)
timeStack.pop(); // 해당 시점 pop
}
timeStack.push(i); // 현재 시점 push
}
while(!timeStack.empty()) { // 끝까지 가격이 떨어지지 않은 나머지 경우들 처리
answer[timeStack.top()] = (N-1) - timeStack.top(); // 떨어지지 않은 기간 계산 (종료 시점 - 해당 시점)
timeStack.pop(); // 처리 완료된 해당 시점 pop
}
return answer;
}
Author And Source
이 문제에 관하여([프로그래머스] 주식가격 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dianestar/프로그래머스-주식가격저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)