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

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요. 강의 잘 듣고 있습니다.

강의 풀이 참고하여 코드 작성하였는데.

ans.push_back({it-LIS.begin(), A[i]});

라인의 위치에 따라 "it-LIS.begin()"의 값이 쓰레기값일 때도 있고 그래서.., 현상의 이유가 궁금합니다.

ans.push_back()을 뒤에 위치시켰을때, pos_ 값이 쓰레기값이 되는 이유 질문드려요.

그 이유로,

LIS.push_back(A[i]); 가 수행되고 나면 LIS.begin()의 주소값이 변경되는 것으로 생각되는데, 맞을까요?

전체 코드>>

#include <bits/stdc++.h>

using namespace std;

int N;
vector<int> A;
vector<int> LIS, Ret;
int len;

vector<pair<int, int>> ans;

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

    cin >> N ;
    A = vector<int>(N,0);
    for(int i =0 ; i < N ; ++i) cin >> A[i];

    for(int i = 0 ; i < N ; ++i){
        auto it = lower_bound(LIS.begin(), LIS.end(), A[i]);

        ans.push_back({it-LIS.begin(), A[i]});
        /* 현재 위치에서 push_back 하였을 떄: 
          >> ans 배열에 담긴 값:
          ans = {
                    {0, 10}
                    {1, 20}
                    {0, 10}
                    {2, 30}
                    {1, 20}
                    {3, 50}
                }
        */

        if (it == LIS.end()) LIS.push_back(A[i]);
        else *it = A[i];

        /* 아래 위치에서 push_back 하였을 떄(주석): 
          ans.push_back({it-LIS.begin(), A[i]});
          >> ans 배열에 담긴 값:
          ans = {
                    {-1405095968, 10}
                    {-7, 20}
                    {0, 10}
                    {10, 30}
                    {1, 20}
                    {3, 50}
                }
        */
    }   


    cout << "디버깅" << endl;
    for(auto a : ans) cout << a.first << " " << a.second << endl;
    cout << endl;

    int len = LIS.size();
    cout << len << endl;

    // 배열을 trace 
    for(int i = N-1 ; i >= 0 ; --i){
        if (ans[i].first == len-1){
            Ret.push_back(ans[i].second);
            len--;
        }
    }

    reverse(Ret.begin(), Ret.end());
    for(auto r: Ret) cout << r << " ";
    cout << endl;

    return 0;
}