๐ Coding Test Study/Algorithm Problem
[C++][Programmers][์คํ/ํ] ์ฃผ์๊ฐ๊ฒฉ
ibelieveinme
2023. 6. 4. 20:15
728x90
https://school.programmers.co.kr/learn/courses/30/lessons/42584
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
*๋ฌธ์ ์ค๋ช
์ฃผ์ ๊ฐ๊ฒฉ์ด ๋์์๋ prices ๋ฒกํฐ๊ฐ ์ฃผ์ด์ง๊ณ , ๊ฐ ์ข ๋ชฉ๋ค์ด ๋ช์ด๊ฐ ๊ฐ๊ฒฉ์ด ๋จ์ด์ง์ง ์์๋์ง๋ฅผ ๋ฐํํ๋ฉด ๋๋ค.
stack/queue ๋ฌธ์ ์ ์์ด์ ๋ณธ ์๋ฃ๊ตฌ์กฐ๋ฅผ ํ์ฉํด๋ณด๋ ค๊ณ ํ์ง๋ง ์ฐ์ ์ด๋ป๊ฒ ๋ฌธ์ ๋ฅผ ํธ๋์ง๋ฅผ ์๊ธฐ ์ํด 2์ค for๋ฌธ์ผ๋ก ๋จ์ํ๊ฒ ๊ตฌํํ๋ค.
* ์์๋ ๊ฒ
stack์ผ๋ก ํผ ๊ฒ.
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices) {
vector<int> answer(prices.size());
stack<int> s;
int size = prices.size(); // ๊ณ์ size๋ฅผ ๊ณ์ฐํ๋ ๊ฒ๋ณด๋ค ์์๊ฐ์ผ๋ก ์ ์ฅํ๋ฉด ์ ์ฒด ํจ์ ์ฒ๋ฆฌ ์๊ฐ ๊ฐ์
for (int i = 0; i < 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()] = size - 1 - s.top(); // ์ข
๋ฃ ์๊ฐ - ๋น์ ์๊ฐ
s.pop();
}
return answer;
}
* ์ฝ๋
#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;
}
728x90