풀이
숫자를 스택에 쌓으면서 비교하면 되는 문제다.
내 숫자보다 큰 숫자가 뒤에 오는지를 구하면 되기 때문에 스택의 맨 위에 있는 수보다 작은 숫자가 오면 스택의 위에 쌓고 큰 수가 오면 스택의 맨 위에 있는 숫자가 뒷 큰 수를 찾았기 때문에 뒷 큰수를 기록하고 스택에서 제거한다.
그리고 새로 맨 위에 오는 숫자가 현재 숫자 보다 큰 지 비교하는 과정을 반복한다.
[아이디어 정리]
1. 스택의 맨 위에 숫자가 현재 숫자보다 큰 지 비교하고, 작으면 스택의 맨 위에 쌓는다.
2. 만약 클 경우 스택의 맨 위의 숫자를 제거하고 뒷 큰수를 기록한 다음 다시 스택의 맨 위 숫자와 비교한다.
3. 위 과정을 반복한다.
Code
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> numbers) {
vector<int> answer(numbers.size(),-1);
vector<pair<int,int>> stack;
pair<int,int> nowPair,cPair;
nowPair=make_pair(0,numbers[0]);
stack.push_back(nowPair);
for (int i=1; i<numbers.size(); i++)
{
while (stack.size()>0)
{
cPair=stack.back();
if (cPair.second>=numbers[i])
{
break;
}
else
{
stack.pop_back();
answer[cPair.first]=numbers[i];
}
}
nowPair=make_pair(i,numbers[i]);
stack.push_back(nowPair);
}
return answer;
}
아이디어가 바로 생각이 안나면 생각보다 오래 걸릴 수도 있는 문제였던 것 같다.
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
반응형
'Algorithm > 프로그래머스' 카테고리의 다른 글
[프로그래머스/C++] 이중우선순위큐 (0) | 2024.01.06 |
---|---|
[프로그래머스/C++] 길 찾기 게임 (0) | 2024.01.06 |
[프로그래머스/C++] 연속된 부분 수열의 합 (0) | 2024.01.06 |
[프로그래머스/C++] 에어컨 (feat.Python) (0) | 2024.01.06 |
[프로그래머스/C++] [3차] n진수 게임 (0) | 2024.01.06 |