[Programmers/C++] 뒤에 있는 큰 수 찾기

 

⏱ 시간 초과

 

테스트 14번부터 시간복잡도가 급격하게 증가한다.

DP를 이용해서 데이터 비교 및 탐색 시간을 줄이는 방법으로 해결하였다.

 

문제

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

 

제한 사항

 

 

 

 

 

입출력 예시

입출력 예시

 

입출력 예시

 

 

 

---

 

풀이 

이 풀이는 뒤에서부터 탐색하는게 핵심이다. 

가장 큰 값은 answer에 기억해두면, 다음 턴에 뒷부분을 다시 탐색 할 필요가 없어진다.

#include <vector>
using namespace std;

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    
    for (int i = numbers.size() - 2; i >= 0; i--) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers[i] < numbers[j]){
                answer[i] = numbers[j];
                break;
            }
            else if (numbers[i] >= numbers[j]){
                if (answer[j] == -1) {
                    break;
                }
                else if (numbers[i] < answer[j]) {
                    answer[i] = answer[j];
                    break;
                }
            }
        }
    }
    
    return answer;
}

 

 

 

---