[C++/PGS] Lv.2 : 뒤에 있는 큰 수 찾기

 

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

프로그래머스

---

프로그래머스 레벨2.

 

1. 첫 시도 : 94.6점 (테케 20, 22번 시간초과)

 

뒤에서부터 탐색하면서, 최댓값을 갱신해주고

작은 수를 만나면 그 위치부터 최댓값까지의 범위에서만 for문을 돌려주었다.

그랬더니 37개 중에 2개 틀려서..실패🥹 시간을 더 줄여야 한다!!!

 

2. 두번째 시도 - 성공 💯💯💯

내 기존 코드에서 오래걸리는 경우가 [10, 1, 1, 1, 1, 1, 1, 1, ... 1, 12] 이런 경우일 거라고 추정했다.

그래서, 연결리스트 느낌으로 각 인덱스가 본인보다 뒤에있는 큰 수의 위치를 가지고 있다면

반복문에서 위치 이동을 통해 더 효율적인 탐색이 가능할 것이라고 생각했다.

그 결과는 100점!!! 

 

 

나의 풀이

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

vector<int> solution(vector<int> numbers) {
    vector<int> answer(numbers.size(), -1);
    int max = numbers[numbers.size()-1];
    int maxIdx = numbers.size()-1;
    int next[1000001] = {-1,}; // 나 다음으로 큰 수의 위치를 연결리스트로 저장
    
    for(int i=numbers.size()-2; i>=0; --i){
        if(numbers[i] >= max){
            max = numbers[i];
            maxIdx = i;
            next[i] = maxIdx;
        }
        else{
            for(int j=i+1; j<=maxIdx; ++j){
                if(numbers[i]<numbers[j]) {
                    answer[i] = numbers[j];
                    next[i] = j;
                    break;
                }
                else{
                    j = next[j]-1;
                }
            }
        }
    }
    return answer;
}