[프로그래머스] 뒤에 있는 큰 수 찾기 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

현재 들고 있는 수에 대한 정보는 (값, 인덱스)이다.

이 수를 스택에 넣을 것이다.

그냥 넣는 게 아니다.

앞서 들어 있는 스택의 수보다 큰 값이라면, 앞서 들어 있는 수의 뒷 큰 수는 현재 내가 들고 있는 수가 된다.

스택에 들어있는 수의 뒷 큰수를 계속 계산하여 현재 들고 있는 수보다 같거나 큰 수가 스택의 top에 있을 때까지 반복한다.

그리고 스택에 푸쉬한다. 현재 들고 있는 값이 푸시되었을 때 그 값 아래의 스택 값들은 현재 들고 있는 값보다 큰 수들밖에 없을 것이다.

 

이 루틴을 반복한다.

배열 모든 값들을 반복문으로 다 돌고도

스택에 남아있는 값들은 뒷 큰수가 없는 값들이다. 마지막으로 스택에 든 값들의 뒷 큰 수를 -1로 초기화해주자.

 

 

프로그래머스에서 아래의 에러가 발생했다면?

signal: segmentation fault (core dumped)

 

스택에 잘못된 접근을 해서 그렇다.

if(numbers[i]<=s.top().first || s.empty())

s.top에 접근하는데 스택이 비어있는지 우선 먼저 확인을 해야 한다.

스택이 비었는데 top에 접근하는 건 잘못된 접근이다.

 

if(s.empty()||numbers[i]<=s.top().first) 

위의 코드처럼 미리 스택에 값이 들었는지 확인하자.

 

전체 코드

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size());
    stack<pair<int,int>> s; // (값, 인덱스)
    
    for(int i=0; i<numbers.size(); i++) {
    
    	// 스택이 비었거나, numbers[i]이 top보다 작거나 같다면
        if(s.empty()||numbers[i]<=s.top().first) {
            s.push(make_pair(numbers[i], i));
        } else {
        
        	// numbers[i]이 top보다 크다면
            while(!s.empty()&&numbers[i]>s.top().first) {
            // numbers[i]이 top보다 작거나 같을때까지
            // 스택에 들어있는 값의 뒷 큰수 설정해준다.
                int value = s.top().first;
                int idx = s.top().second;
                s.pop();
                answer[idx] = numbers[i];
            }
            
            // while문 끝나면 numbers[i] 값 스택에 넣어주기.
            s.push(make_pair(numbers[i], i));
        }
    }
    
    // 스택에 남은 값들은 제일 큰 값이거나 맨 뒤에 위치한 수
    // 스택에 남은 값들의 뒷 큰수를 -1로 설정해준다.
    while(!s.empty()) {
        int idx = s.top().second;
        s.pop();
        answer[idx] = -1;
    }
    
    return answer;
}