인프런 커뮤니티 질문&답변

이중 백터를 만들어서 수열을 저장하는 저장하는 방법을 사용했는데.. 정답은 잘 나오는 거 같은데 메모리 초과가 뜹니다 ㅠㅠ 이 코드를 개선하여 통과하기는 어려울까요?

다른 풀이들도 보니 역추적 방법으로만 풀더라구요

시험이라고 생각하면, 역추적 아이디어를 번뜩 떠올리기는 힘들 수도 있다는 생각도 드네요..

#include <bits/stdc++.h>
using namespace std; 

int N, tmp, cnt;
vector<int> v;
vector<vector<int>> answer(1000001);

int binary_search(int num){
    long low = 0, high = v.size() - 1; 

    while(low <= high){
        long mid = (low + high) / 2;

        if(v[mid] == num){
            return mid;
        } 
        else if(v[mid] >= num){ // 배열의 값이 더 크다. 줄여야 한다
            high = mid - 1;
        }
        else{ // 배열의 값이 더 작다. 늘려야 한다
            low = mid + 1;
        }
    }

    return low; // 배열보다 이상인 인덱스 리턴
}

int main() {
    ios_base:: sync_with_stdio(false);
    cin.tie (NULL); cout.tie (NULL);

    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> tmp;
        
        if(v.empty()){
            v.push_back(tmp); 
            answer[0].push_back(tmp);
            continue;
        }
        
        if(v.back() < tmp){
            v.push_back(tmp);
            cnt++;

            if(i > 0){
                answer[cnt] = answer[cnt-1];
                answer[cnt].push_back(tmp);
            }
        }
        else if(v.back() > tmp){
            int idx = binary_search(tmp);
            v[idx] = tmp;

            if(idx > 0){
                answer[idx] = answer[idx-1];
                answer[idx].push_back(tmp);
            }
            else{
                answer[0].clear();
                answer[0].push_back(tmp);
            }
        }
    }

    cout << v.size() << "\n";

    for(int i = 0; i < answer[v.size()-1].size(); i++){
        cout << answer[v.size()-1][i] << " ";
    }
}