본문 바로가기
Algorithm/프로그래머스

[프로그래머스/C++] 뒤에 있는 큰 수 찾기

by code_pie 2024. 1. 6.

 

 

풀이

 

숫자를 스택에 쌓으면서 비교하면 되는 문제다.

 

내 숫자보다 큰 숫자가 뒤에 오는지를 구하면 되기 때문에 스택의 맨 위에 있는 수보다 작은 숫자가 오면 스택의 위에 쌓고 큰 수가 오면 스택의 맨 위에 있는 숫자가 뒷 큰 수를 찾았기 때문에 뒷 큰수를 기록하고 스택에서 제거한다.

 

그리고 새로 맨 위에 오는 숫자가 현재 숫자 보다 큰 지 비교하는 과정을 반복한다.

[아이디어 정리]

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

 

반응형