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

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/154539

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

해결전략

 

stack 스택

 

 

 

---

 

처음 시도한 코드- 시간초과 

 

#include <string>
#include <vector>
using namespace std;
 
vector<int> solution(vector<int> numbers) {
    vector<int> answer;
 
    for(int i=0; i<numbers.size(); i++)
    {
        int currAnsSize = answer.size();
        
	    for(int j=i+1; j<numbers.size(); j++)
	    {
		    if(numbers[i] < numbers[j]){
                answer.emplace_back(numbers[j]);
                break;
		    }
	    }
 
        // 검사하는 수 뒤에 더 큰 수가 없는 경우 위에서 answer에 삽입이 되지 않아 answer 사이즈가 변하지X 
        if(currAnsSize == answer.size()) {
            answer.emplace_back(-1); // 뒤에 더 큰 수가 없는 경우 -1 삽입
        }
    }
 
    return answer;
}

 

---

 

정답 코드

 

#include <stack>
#include <vector>
using namespace std;
 
vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1); // 초기값은 -1로 설정
    stack<int> stk;
 
    for(int i=0; i<numbers.size(); i++)
    {
        // 만약 스택이 비어있지 않고, 현재 인덱스의 값이 스택의 top에 해당하는 인덱스의 값보다 크다면,
        // 즉, 현재 숫자가 이전 숫자보다 큰 경우에는
       while (!stk.empty() && numbers[stk.top()] < numbers[i])
       {
			// answer 벡터에서 해당 위치(즉, 이전 숫자의 위치)에 현재 값을 할당.
           // 이렇게 하면, 각 요소 뒤에 있는 첫 번째 큰 수가 할당됩니다.
           answer[stk.top()] = numbers[i];
           stk.pop(); // 그 값을 처리했으므로 스택에서 pop하여 제거합니다
       }
       stk.push(i); //현재 인덱스를 스택에 push. 이는 아직 다음에 오는 더 큰 수를 찾지 못했다는 것을 의미.
    }
    
    return answer;
}
 
int main()
{
    vector<int> testcase1 = { 2, 3, 3, 5 };
    vector<int> testcase2 = { 9, 1, 5, 3, 6, 2 };
 
    solution(testcase2);
 
    return 0;
}

 

 

---