[ ๋ฌธ์ ๋งํฌ ]
https://school.programmers.co.kr/learn/courses/30/lessons/154539#
๐ฉ ์กฐ๊ฑด
- ์ ์๋ก ์ด๋ฃจ์ด์ง ๋ฐฐ์ด numbers
- ๋ฐฐ์ด์ ๊ฐ ์์๋ค์ ๋ํด ์์ ๋ณด๋ค ๋ค์ ์๋ ์ซ์ ์ค์์ ์์ ๋ณด๋ค ํฌ๋ฉด์ ๊ฐ์ฅ ๊ฐ๊น์ด ์๋ ์๋ฅผ ๋ท ํฐ์๋ผ๊ณ ํจ
- ๋ชจ๋ ์์์ ๋ํ ๋ท ํฐ์๋ค์ ์ฐจ๋ก๋ก ๋ด์ ๋ฐฐ์ด์ returnํด๋ผ. ๋ท ํฐ์ ์์ผ๋ฉด -1 ๋ด์๋ผ.
๐ฉ ์ ๊ทผ
์ด๊ฑธ ์คํ์ ์ด์ฉํด์ ํ์ด์ผ ํ๋ค๋ ๊ฑธ ๋ ์ฌ๋ฆฌ๊ธฐ๊ฐ ์ฝ์ง ์๋ค..
๐ฉ ์ํ์ฐฉ์ค
์ฒ์์๋ 2์ค for๋ฌธ์ผ๋ก ๊ตฌํํ๋ค. ๋น์ฐํ๊ฒ๋ ๋ง์ง๋ง ํ ์คํธ์ผ์ด์ค 4๊ฐ์์ ์๊ฐ ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค.
์๊ฐ ์ด๊ณผ์ ์์ธ์ด ์ด๋ฏธ ์ดํด๋ดค๋ ๊ฑธ ๋ฐ์์ ๋ชปํ๊ณ ๋ค์ ๋ ์ดํด๋ณด๊ธฐ ๋๋ฌธ์ด๋ผ๊ณ ์๊ฐํด์ ๋ฐฐ์ด์ ๋ค์์๋ถํฐ ๋ด์ผํ ๊ฒ ๊ฐ๋ค๊ณ ์๊ฐํ๋ค.
์ด์ฌํ ๊ณ ๋ฏผํด์ ๋ญ๊ฐ ๊ทธ๋ด๋ฏํ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ ธ๋ค. numbers[i]๊ฐ numbers[i+1]๋ณด๋ค ํฌ๋ฉด answer[i+1]๊ณผ ๋น๊ตํด์ ๊ทธ๊ฒ๋ณด๋ค๋ ํฌ๋ฉด -1, ๊ทธ๋ ์ง ์์ผ๋ฉด numbers[i+1], numbers[i]๊ฐ numbers[i+1]๋ณด๋ค ์์ผ๋ฉด numbers[i]๋ฅผ ๋ด์..
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> numbers) {
vector<int> answer;
for(int i=0; i<numbers.size(); i++){
answer.push_back(-1);
}
for(int i=numbers.size()-2; i>=0; i--){
if(numbers[i]>=numbers[i+1]){
if(numbers[i]>=answer[i+1]){
answer[i]=-1;
for(int j=i+1; j<numbers.size()-1; j++){
if(numbers[i]<answer[j]){
answer[i]=answer[j];
break;
}
}
}
else
answer[i]=answer[i+1];
}else{
answer[i]=numbers[i+1];
}
}
return answer;
}
์ด๋ ๊ฒ ํ๋ฉด ํ ์ผ 2๊ฐ๊ฐ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๋ค. ์๋ง๋ ์ ๋ด๋ถ for๋ฌธ ๋๋ฌธ์ผ ๊ฒ์ด๋ค.
์๊ฐ์ด๊ณผ ์์ด ๊ตฌํํ๋ ค๋ฉด ์คํ์ ํ์ฉํด์ผ ํ๋ค.
for๋ฌธ์ ํตํด numbers๋ฅผ ๋ค์์๋ถํฐ ๊ฑฐ๊พธ๋ก ํ์ํ๋ฉฐ, numbers[i]์ ๋ํด
- ์คํ์ด ๋น์ด์์ผ๋ฉด answer[i]=-1, numbers[i]๋ฅผ ์คํ์ push
- ์คํ์ top๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ผ๋ฉด ์คํ์ top์ด numbers[i]๋ณด๋ค ํด๋๊น์ง pop
- ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์๊ฐ ๋์ค๋ฉด answer[i]=์คํ์ top, numbers[i]๋ฅผ ์คํ์ push
- ์คํ์ top๋ณด๋ค ์์ผ๋ฉด answer[i]=์คํ์ top, numbers[i]๋ฅผ ์คํ์ push
๐ป ์ฝ๋ (C++)
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> numbers) {
vector<int> answer;
for(int i=0; i<numbers.size(); i++){
answer.push_back(-1);
}
stack<int> stack;
for(int i=numbers.size()-1; i>=0; i--){
if(stack.empty())
stack.push(numbers[i]);
else{
if(numbers[i]>=stack.top()){
while(!stack.empty() && numbers[i]>=stack.top()){
stack.pop();
}
if(!stack.empty()) answer[i] = stack.top();
stack.push(numbers[i]);
}
else{
answer[i] = stack.top();
stack.push(numbers[i]);
}
}
}
return answer;
}
STL์ stack ์ด์ฉํ๋ฉด top(), pop() ์ฌ์ฉ ๊ฐ๋ฅ
'๐ป Algorithms > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ์ต๋๊ฐ๊ณผ ์ต์๊ฐ - ๋ฌธ์์ด ์ฒ๋ฆฌ? (1) | 2024.09.20 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ฌ๋ฆฌ๊ธฐ ๊ฒฝ์ฃผ - ํด์ (0) | 2024.09.20 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ง๋ฒ์ ์๋ฆฌ๋ฒ ์ดํฐ - ์ํ (0) | 2024.08.23 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ ์ ์ฌ์ด์ ์ ์ ์ - ์ํ (0) | 2024.08.17 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์ฐ์๋ ๋ถ๋ถ ์์ด์ ํฉ - ํฌ ํฌ์ธํฐ (0) | 2024.08.14 |