[P5] 백준 가장 긴 증가하는 부분 수열 5 C++ 이분 탐색, lower_bound

리뷰

lower_bound를 통해 가장 긴 증가하는 부분 수열을 만들고, 해당 수열의 길이와 변경 내역 정보를 저장 및 역추적 하여 LIS를 출력하는 문제

https://www.acmicpc.net/problem/14003

관련 문제

가장 긴 증가하는 부분 수열 4 : https://www.acmicpc.net/problem/14002

 

문제 풀이

1. n과 100만 크기 정수 배열 nums, 정수형 벡터 temp, lis를 전역 변수로 초기화 해준다.
2. n값을 입력 받고 nums에 각 수열 정보를 입력 받은 뒤 BS 함수를 실행 시켜준다.
3. pos벡터를 n크기로 초기화 해 준 뒤 n개의 숫자를 모두 탐색해 준다.
4. 만약 temp에 i번째 수이상이 존재한다면 해당 위치를 i로 바꿔준다. 없다면 temp의 뒤에 i를 추가해 준다.
5. 매 작업 시마다 i번째 수가 temp에 삽입된 위치를 pos배열에 기록을 해준다.
6. LIS를 구하는 작업을 마친 후에는 temp 벡터의 길이를 먼저 출력을 해준다.
7. 이후 LIS를 구하기 위해 역추적 작업이 필요하다, 인덱스 용으로 currentLength를 length - 1값으로 초기화 해준다.
8. n - 1번째 인덱스부터 0번째 인덱스까지 순회를 하며 pos의 i번째 값이 currentLength와 같다면 lis 벡터에 nums[i]를 추가해 준 뒤 currentLength를 1 감소시켜 준다.
9. push_back을 통해 lst벡터에 추가를 했으므로 최종적으로 배열을 뒤집어 주어야 한다.
10. lis 배열에 저장된 값을 출력해 주면 된다.

 

참고 사항

백준 12015번 가장 긴 증가하는 부분 수열 2와 비슷하지만 해당 문제는 부분 수열의 길이 뿐만 아니라 직접 부분 수열을 출력해 주어야 한다.

 

[G2] 백준 12015번 가장 긴 증가하는 부분 수열 2 C++ 이분 탐색, lower_bound

 

시뮬레이션 정보를 추가해 주겠다.

입력

10
10 9 1 8 2 7 3 6 4 5

 

시뮬레이션

주어진 수열은: 10, 9, 1, 8, 2, 7, 3, 6, 4, 5

1. LIS 길이 계산 및 pos 기록

Step-by-Step:

1. 첫 번째 숫자 10:
   • temp 배열은 비어 있으므로 10을 추가.
   • pos[0] = 0 (첫 번째 위치에 해당)
   temp = [10] pos = [0, _, _, _, _, _, _, _, _, _]
2. 두 번째 숫자 9:
   • lower_bound(temp, 9)는 0번 인덱스(temp[0] = 10)에 위치.
   • temp[0]을 9로 대체.
   • pos[1] = 0 (여전히 첫 번째 위치에 해당)
   temp = [9] pos = [0, 0, _, _, _, _, _, _, _, _]
3. 세 번째 숫자 1:
   • lower_bound(temp, 1)는 0번 인덱스(temp[0] = 9)에 위치.
   • temp[0]을 1로 대체.
   • pos[2] = 0 (첫 번째 위치에 해당)
   temp = [1] pos = [0, 0, 0, _, _, _, _, _, _, _]
4. 네 번째 숫자 8:
   • lower_bound(temp, 8)는 temp.end()에 위치(새로운 값 추가).
   • temp에 8을 추가.
   • pos[3] = 1 (두 번째 위치에 해당)
   temp = [1, 8] pos = [0, 0, 0, 1, _, _, _, _, _, _]
5. 다섯 번째 숫자 2:
   • lower_bound(temp, 2)는 1번 인덱스(temp[1] = 8)에 위치.
   • temp[1]을 2로 대체.
   • pos[4] = 1 (두 번째 위치에 해당)
   temp = [1, 2] pos = [0, 0, 0, 1, 1, _, _, _, _, _]
6. 여섯 번째 숫자 7:
   • lower_bound(temp, 7)는 temp.end()에 위치.
   • temp에 7을 추가.
   • pos[5] = 2 (세 번째 위치에 해당)
   temp = [1, 2, 7] pos = [0, 0, 0, 1, 1, 2, _, _, _, _]
7. 일곱 번째 숫자 3:
   • lower_bound(temp, 3)는 2번 인덱스(temp[2] = 7)에 위치.
   • temp[2]을 3으로 대체.
   • pos[6] = 2 (세 번째 위치에 해당)
   temp = [1, 2, 3] pos = [0, 0, 0, 1, 1, 2, 2, _, _, _]
8. 여덟 번째 숫자 6:
   • lower_bound(temp, 6)는 temp.end()에 위치.
   • temp에 6을 추가.
   • pos[7] = 3 (네 번째 위치에 해당)
   temp = [1, 2, 3, 6] pos = [0, 0, 0, 1, 1, 2, 2, 3, _, _]
9. 아홉 번째 숫자 4:
   • lower_bound(temp, 4)는 3번 인덱스(temp[3] = 6)에 위치.
   • temp[3]을 4로 대체.
   • pos[8] = 3 (네 번째 위치에 해당)
   temp = [1, 2, 3, 4] pos = [0, 0, 0, 1, 1, 2, 2, 3, 3, _]
10. 열 번째 숫자 5:
    • lower_bound(temp, 5)는 temp.end()에 위치.
    • temp에 5를 추가.
    • pos[9] = 4 (다섯 번째 위치에 해당)
    temp = [1, 2, 3, 4, 5] pos = [0, 0, 0, 1, 1, 2, 2, 3, 3, 4]

결과:

temp = [1, 2, 3, 4, 5]는 최종 LIS의 길이를 나타내며, pos 배열에는 각 숫자가 temp에서 몇 번째 위치에 있는지를 나타낸다.

2. LIS 복원 과정

temp의 크기는 5이므로, LIS의 길이는 5입니다. 이제 pos 배열을 사용하여 뒤에서부터 LIS를 복원

역추적:

• currentLength = 4로 시작하여, pos[i]와 currentLength가 일치하는 숫자를 찾는다.

1. i = 9: pos[9] = 4 → 5는 LIS의 일부. currentLength-- (3).
2. i = 8: pos[8] = 3 → 4는 LIS의 일부. currentLength-- (2).
3. i = 7: pos[7] = 3 (이미 4를 선택했으므로 패스).
4. i = 6: pos[6] = 2 → 3는 LIS의 일부. currentLength-- (1).
5. i = 5: pos[5] = 2 (이미 3을 선택했으므로 패스).
6. i = 4: pos[4] = 1 → 2는 LIS의 일부. currentLength-- (0).
7. i = 3: pos[3] = 1 (이미 2를 선택했으므로 패스).
8. i = 2: pos[2] = 0 → 1은 LIS의 일부. currentLength-- (-1).

역추적한 결과 lis = [5, 4, 3, 2, 1]가 됩니다. 이를 뒤집으면 최종 LIS는 [1, 2, 3, 4, 5]

 

출력

5
1 2 3 4 5

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, nums[1000000];
vector<int> temp, lis;

void BS() {
    vector<int> pos(n);  // 각 원소가 temp에서 위치한 인덱스를 기록할 배열
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(temp.begin(), temp.end(), nums[i]);
        int idx = it - temp.begin();

        // temp에 값을 업데이트하거나 추가
        if (it == temp.end()) temp.push_back(nums[i]);
        else *it = nums[i];

        // 해당 숫자가 temp의 어느 위치에 들어갔는지 기록
        pos[i] = idx;
    }

    // LIS 길이를 미리 저장
    int length = temp.size();
    cout << length << "\n";

    // LIS를 복원하기 위한 역추적
    int currentLength = length - 1;
    for (int i = n - 1; i >= 0; i--) {
        if (pos[i] == currentLength) {
            lis.push_back(nums[i]);
            currentLength--;
        }
    }

    // LIS를 뒤집어서 출력
    reverse(lis.begin(), lis.end());
    for (int l : lis) cout << l << " ";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> nums[i];
    BS();
}