[Lv 2] 뒤에 있는 큰 수 찾기

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

프로그래머스

 

처음 문제를 접하고 이중 반복을 사용해 해결하고자 하였다.

이중 반복을 사용하면 최악의 경우 1,000,000^2의 반복을 실행해야 하기 때문에 대략 2초가 걸릴 수 있다.

따라서 시간 초과가 발생 하였다.

 

이 문제를 해결하기 위해선 배열 2개를 사용해야한다.

answer 배열은 numbers 배열과 같은 크기로 할당하고 -1로 초기화한다. 

다음 인덱스를 저장할 배열을 생성한다.

현재 검사할 값이 인덱스를 저장한 배열의 마지막 요소보다 크면 answer 배열에 그 값을 저장한다.

 

#include <string>
#include <vector>

using namespace std;
int N;

vector<int> solution(vector<int> numbers) {
    N = numbers.size();
    vector<int> answer(N, -1);
    vector<int> v;
    for(int i = 0;i < N;i++){
        while(!v.empty()&&numbers[i]>numbers[v.back()]){
            answer[v.back()] = numbers[i];
            v.pop_back();
        }
        
        v.push_back(i);
    }
    return answer;
}