[ 백준 14003 ] 가장 긴 증가하는 부분수열5 (C++)

백준의 가장 긴 증가하는 부분수열5(14003) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

이 문제를 풀기전에, 그리고 이 글을 읽어보시기 전에 다음 링크에 걸려있는 문제를 먼저 풀어보고 오시는 것과 풀이까지 보고 오시는 것을 상당히 많이 권장드립니다.

[ 가장 긴 증가하는 부분수열3(12738) - 문제 바로가기 ]

[ 가장 긴 증가하는 부분수열3(12738) - 풀이 바로가기 ]

이 글에서는 위의 링크에 걸려있는 풀이방법과 굉장히 유사한 방법으로 그리고 했던 말들을 다시 하는 방식으로 문제 풀이를 진행할 것이다. 그래서 위의 글을 읽고 오지 않으면, 아래의 글이 이해가 잘 되지 않을 수도 있다. 그러니 반드시 ! 먼저 풀어보고 오는 것을 권장한다.

 

이 문제 또한, 위에 링크를 걸어놓은 12738번 문제와 동일하게, 주어진 배열의 최대크기가 너무 크기 떄문에, 단순히 O(N^2)의 풀이 방법으로는 해결할 수 없고, O(NlogN) 만에 해결하는 방식으로 구현을 해야 한다.

그래서 위의 12738번 문제풀이와 동일하게, O(NlogN) 시간만에 가장 긴 증가하는 부분 수열의 길이는 구할수가 있다.

그런데 ! 문제는 "길이만" 구할 수 있다는 것이다.

12738번 풀이 마지막 부분에서 실제로 LIS배열에 저장된 데이터들을 다 출력시켜보면, 조금은 엉뚱한 배열이 출력된다는 것을 이야기를 했었다. 그런데 이 문제에서는 정확한 LIS를 출력해야 한다는 것이다. 따라서 ! 이 풀이에서는 정확한 LIS를 출력하는 과정에 대해서 알아보자.

 

전체적인 풀이는 12738번 문제풀이와 동일하다. LIS 수열을 저장할만한 새로운 저장공간(벡터 or 배열)을 선언해서, 이분탐색을 통해서 적절한 위치를 찾아가면서 LIS수열을 채워갈 것이다.

그런데 ! 우리는 여기서 딱 한가지를 더 추가할 것이다. 바로 "데이터가 들어가는 Index위치를 저장" 하는 과정이다.

그럼 여기까지만 이야기하고 하나의 예시를 가지고 진행해보자.

지금부터 사용할 수식부터 정리를 해보겠다.

Arr[] = 입력으로 주어지는 배열을 저장하는, 원본의 데이터를 가지고 있는 배열

LIS[] = 증가하는 부분 수열을 저장하는 배열

Index[] = 이번 문제에서 추가된, "데이터가 들어가는 Index의 위치를 저장" 하는 배열.

Index[A] = B : "원본 데이터에서 A번째에 있는 숫자는, LIS배열에서 B번째에 위치합니다."

예시는 예제입력으로 주어진 Arr[] = { 10 , 20 , 10 , 30 , 15 , 50 } 으로 진행해보자.

지난글과 마찬가지로, LIS배열을 채울 때는, "숫자(x)"의 형식으로 채우겠다. 숫자(x)의 의미는, "이 숫자는 원본 배열에서 x번째에 존재하던 값이였습니다." 를 의미한다.

( 중간중간, LIS배열을 채우기 위해서 적절한 위치를 찾는 과정은 지난번 글에서 자세하게 다뤘기 때문에, 이번 글에서는 간략하게만 이야기하고 넘어가겠습니다. )

 

1. 가장 첫 번째 값 : '10'

첫 번째 값이기 때문에 비교할 대상도, 적절한 위치를 찾을 필요도 없다. 가장 처음에 넣어주면 된다.

LIS[] = { 10(1) }

그리고 ! 우리가 새로 추가한 "데이터가 들어가는 Index의 위치를 저장"하는 배열도 값을 채워주자.

Index[1] = 1.

Index[1] = 1을 풀이해보면, "원본 데이터에서 1번쨰에 있는 숫자는, LIS배열에서 1번쨰에 위치합니다." 를 의미한다.

실제로, 원본데이터 Arr[] 에서 1번쨰에 있는 숫자는, LIS배열에서 1번째에 위치하게 되었다.

 

2. 두 번째 값 : '20'

LIS배열의 가장 마지막에 넣어주면 된다.

LIS[] = { 10(1) , 20(2) }

Index의 위치를 저장하는 배열도 채워보면, Index[] = { 1 , 2 } 가 된다.

 

3. 세 번째 값 : '10'

LIS배열에 넣어보면, LIS[] = { 10(3) , 20(2) } 가 된다.

그리고, Index의 위치를 저장하는 배열도 채워보면, Index[] = { 1 , 2 , 1 } 이 된다.

왜냐하면, Index[3] = 1 이 되기 떄문이다. 이 수식의 말을 다시한번 적어보면, "원본 수열에서 3번쨰에 존재했던 숫자는, LIS 배열에서는 1번째에 위치합니다." 를 의미한다.

실제로 LIS배열을 보게되면, LIS[] = { 10(3) , 20(2) } 로, 3번째 존재했던 숫자 '10'은, LIS배열에서 1번에 위치하고 있다는 것을 확인할 수 있다.

 

4. 네 번째 값 : '30'

LIS배열에 넣어보면 LIS[] = { 10(3) , 20(2) , 30(4) } 가 된다.

Index의 위치를 저장하는 배열도 채워보면, Index[] = { 1 , 2 , 1 , 3 } 이 된다.

왜냐하면, 원본 수열에서 4번째에 위치하던 숫자 30은, LIS배열에서 3번째에 위치하고 있으므로, Index[4] = 3 이 된다.

 

5. 다섯 번째 값 : '15'

LIS배열에 넣어보면 LIS[] = { 10(3) , 15(5) , 30(4) } 가 된다.

Index의 위치를 저장하는 배열도 채워보면, Index[] = { 1 , 2 , 1 , 3 , 2 } 가 된다.

 

6. 여섯 번째 값 : '50'

LIS배열에 넣어보면 LIS[] = { 10(3) , 15(5) , 30(4) , 50(6) } 이 된다.

Index의 위치를 저장하는 배열도 채워보면, Index[] = { 1 , 2 , 1 , 3 , 2 , 4 } 가 된다.

 

그럼 먼저, 우리가 구해야 하는 값 중, 가장 긴 증가하는 부분 수열의 길이는, LIS배열의 크기를 출력해주면 된다.

LIS배열은 현재 크기가 4인 상태이므로, 가장 긴 증가하는 부분 수열의 길이는 4가 된다.

그럼, 이제 가장 긴 증가하는 부분수열을 출력해보자.

일단, LIS배열을 그대로 출력한다면, 우리가 위에서 직접 채워넣어본 LIS[] 배열만 봐도 알 수 있듯이, 값이 제대로 나오지 않는다는 사실과 왜 그런지는 지난 글에서 다 이야기를 했었다.

제대로 된 수열을 구하기 위해서 우리가 새롭게 저장한, Index의 위치를 저장해놓은 배열을 이용해보자.

일단 결과만 한번 보자면 다음과 같이 되어있다.

.

그리고 정답부터 이야기하면 우리는 { 10 , 20 , 30 , 50 } 이라는 수열을 구해야 하는 것이다.

즉, LIS배열의 첫 번째 값으로는 '10'을, 두 번째 값으로는 '20'을, 세 번째 값으로는 '30'을, 네 번쨰 값으로는 '50'을 선택하게 된다면, 올바른 수열이 된다는 것이다.

그리고 세 번째값인 '30'과 네 번째 값인 '50'은 생각보다 쉽게 결정할 수 있을 것 같아 보인다. 왜냐하면, 위의 표에서 확인할 수 있듯이, LIS의 3번째 값과 4번째 값으로 선택될 수 있는 유일한 값들이기 때문이다.

문제는, 첫 번째 값과 두 번째 값이라는 것이다. 왜냐하면, 선택될 수 있는 후보들이 여러개가 존재하기 때문이다.

그럼 2번 후보인, '20'과 '15'를 한번 비교해보자.

물론, 우리는 정답을 알고 있기 때문에, '20'을 뽑아야 한다는 것을 알고 있다. 그런데 왜 그런지를 알아보자.

'15'를 보게되면, LIS수열에 2번에 올 수 있는 놈이지만, 원본 배열에서의 위치를 보게 되면, 30과 50사이, 즉, 3번째 값에 오는 후보와 4번째 값에 오는 후보 사이에 끼어있다. 즉, 3번째 값으로 오는 놈보다 더 이후에 있는 값이라는 것이다.

그렇기 때문에, 2번째 값으로 올 수 있는 적절한 값이 아닌 것이다.

다시한번 말을 정리해보자. '15'는 우리가 구한 바에 의하면, LIS배열에서 2번 자리에 위치해야 하는 놈이다. 그런데, 실제 배열에서 보면, '15'는 LIS배열에서 3번 자리에 위치하는 놈보다 더 이후에 나오는 값이다. 즉 ! LIS배열에서 2번 자리에 위치할 수 없다는 것을 알 수 있다. 따라서, 2번 자리에 올 수 있는 놈은 '20'이 되는 것이다.

10도 마찬가지이다. 3번에 위치해있는 '10'을 보게되면, LIS배열에서 2번 자리에 위치할 수 있는 20보다 더 이 후에 나오는 것을 확인할 수 있다. 그래서 이 놈은 1번 자리에 위치할 수 가 없게 된다.

그럼 이걸 어떻게 구현할까 ?? Index값을 앞에 놈들이랑 다 비교하면서 구해야할까 ??

아니다. 역순으로 구하면 생각보다 간편하게 구할 수 있다.

우리는 LIS배열의 크기가 '4'라는 것은 알고 있다.

그럼, 위의 배열에서 뒤에서부터 거꾸로 '4번자리에 위치하는 놈', '3번자리에 위치하는 놈', ..... '1번 자리에 위치 하는 놈' 을 찾아보자.

가장 먼저 50이 4번 자리에 위치하는 놈으로 선정되었다. 따라서, 그 다음 자리인 3번 자리에 위치하는 놈을 찾아보자.

'15'를 보니, 2번 자리에 위치하는 놈이기 떄문에, 우리가 현재 찾고자 하는 3번 자리에 위치할 수 있는 숫자가 아니다.

그럼 넘어가자. '30'을 보니, 우리가 현재 찾고자 하는 3번 자리에 위치하는 놈이다. 그럼 30을 선택해주자.

그 다음으로는 2번 자리에 위치하는 놈을 찾아보자. 그 다음 숫자를 탐색해보니 '10'이 나왔는데, 이 놈은 1번자리에 위치할 수 있는 놈이다. 따라서 현재 우리가 찾고자 하는 2번 자리에 올 수 있는 숫자가 아니므로 넘어가자.

그 다음으로 '20'이 나왔는데, 이 놈은 2번 자리에 위치할 수 있는 놈이다. 따라서 선택해주자.

그리고 마지막으로 1번 자리를 찾게 되면 '10'을 찾게 되는 것이다.

그럼 우리가 찾은 숫자들을 찾은 순서대로 적어보면 { 50 , 30 , 20 , 10 } 이 된다. 그런데 ? 우리는 역순으로 숫자들을 찾아왔다. 즉 ! 다시 저 숫자들을 역으로 뒤집어주면 ? 우리가 찾고자 하는 { 10 , 20 , 30 , 50 } 이 나오게 된다.

 

코드에 대한 설명은 따로 하지 않겠다. 왜냐하면 그 과정이, 지난 글에서도 이야기한 과정과 너무나도 많이 비슷하고, 단지 새롭게 추가한 "Index의 위치를 저장하는 놈"만 추가되었기 때문에 따로 설명은 하지 않겠다.

단지 ! 코드를 볼 때 주의해야 할 점은, 이 글에서 설명을 할 때에는 쉽게 설명하기 위해서 1번자리에 위치, 2번 자리에 위치.. 이런식으로 표현을 했지만, 실제 코드에서 배열이나 벡터는 0번 Index부터 존재하기 때문에, 이 점만 주의하면 된다.

 

[ 소스코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
 
#define endl "\n"
#define MAX 1000010
using namespace std;
 
int N;
int Arr[MAX];
int Index_Arr[MAX];
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (V.size() == 0 || V[V.size() - 1] < Arr[i])
        {
            V.push_back(Arr[i]);
            Index_Arr[i] = V.size() - 1;
        }
        else
        {
            int Left = 0;
            int Right = V.size() - 1;
            while (Left < Right)
            {
                int Mid = (Left + Right) / 2;
                
                if (V[Mid] >= Arr[i]) Right = Mid;
                else Left = Mid + 1;
            }
            V[Left] = Arr[i];
            Index_Arr[i] = Left;
        }
    }
    cout << V.size() << endl;
    vector<int> Answer;
    int Find_Index = V.size() - 1;
    for (int i = N; i > 0; i--)
    {
        if (Index_Arr[i] == Find_Index)
        {
            Find_Index--;
            Answer.push_back(Arr[i]);
        }
    }
    for (int i = Answer.size() - 1; i >= 0; i--) cout << Answer[i] << " ";
    cout << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}