[Programmers] Lv2. 뒤에 있는 큰 수 찾기 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

입력 데이터의 크기가 백만 개라 \( O(N^2) \)으로는 풀 수 없습니다. 어떤 자료구조를 쓸까 고민을 많이 했습니다.

문제에서 볼 수 있는 특징들은 다음과 같습니다.

 

1. 입력 데이터를 차례대로 순회 시작
2. 현재 숫자가 뒤의 숫자보다 작다면, 뒤의 숫자는 뒷 큰수이므로 현재 숫자를 해당 뒷 큰수로 교체
3. 현재 숫자가 뒤의 숫자보다 크다면, 뒷 큰수가 있을 수도 없을 수도 있는 숫자이므로 따로 관리
   • 따로 관리되는 이 숫자들은 훗날 뒷 큰수를 만났을 때, 해당 뒷 큰수보다 작은 숫자들을 바꿔야 함

 

여기서 스택(Stack)을 사용하면 좋을 것 같다는 생각을 했었어야 했는데, 제가 아직 문제 분석 능력이 떨어지나 봅니다. 위와 같은 특성들을 바탕으로, 다음 알고리즘을 짜서 구현하였습니다.

 

1. 스택의 데이터는 <숫자, 인덱스>로 구성된다.
2. 제일 처음 데이터인 (numbers[0], 0)를 스택에 넣고, 1번 인덱스부터 끝까지 순회를 시작한다.
3. 현재 숫자가 스택의 최상위 숫자보다 작거나 같을 경우, (현재 숫자, 인덱스)를 스택에 삽입
4. 그게 아니라면 뒷 큰수를 만난 경우이므로, 스택에서 해당 뒷 큰수보다 작은 숫자들은 모조리 뒷 큰수로 변경
   • 그 후, 뒷 큰수인 (현재 숫자, 인덱스)를 스택에 삽입
5. 순회를 다 돌고 스택에 남아 있는 숫자들은 뒷 큰수가 없는 숫자들이므로, 해당 숫자의 인덱스로 찾아가 -1로 변경

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> solution(vector<int> numbers) {
    stack<pair<int, int>> _stack;   // <숫자, 인덱스>
    _stack.push(make_pair(numbers[0], 0));
    
    for(int i = 1; i < numbers.size(); i++)
    {
        if (numbers[i] <= _stack.top().first) {
            _stack.push(make_pair(numbers[i], i));
            continue;
        }
        
        int pivot = numbers[i];
        
        while(!_stack.empty() and _stack.top().first < pivot)
        {
            int index = _stack.top().second;
            numbers[index] = pivot;
            _stack.pop();
        }
        
        _stack.push(make_pair(pivot, i));
    }
    
    // 뒷 큰수가 없는 숫자들 -1로 변경
    while(!_stack.empty()) {
        auto element = _stack.top();
        numbers[element.second] = -1;
        _stack.pop();
    }
    
    return numbers;
}

 

제출 결과