[알고리즘][16][백준_7570] - 줄 세우기

 

전략

 

N의 최대크기는 100만이므로 배열이 주어졌을 때 한명한명 맨 앞 또는 맨 뒤로 전부 보내보는 것은 불가능해 보인다.

 

따라서 다른 전략이 필요할 것 같았다.

 

이런 문제처럼 감이 잘 안올 때에는 간단한 예제를 통해서 대략적인 전략을 찾아야 한다.

 

먼저 문제에서 주어진 예제를 먼저 보자.

 

 

예제의 입력에 대해서 답을 도출하는 과정은 위와 같다.

 

이 예제에서 주목한 부분은 "움직인 숫자" 와 "움직이지 않은 숫자" 였다.

 

아래와 같이 구분하면 좀 더 보기 쉬울 것이다.

 

 

2와 3은 그대로 두었고 5,4,1은 앞 또는 뒤로 옮겼다.

 

왜 2,3은 두고 5,4,1만 옮겼을 때 최소의 움직임이 되는지를 고민해보았다.

 

이 예제만으로는 감이 잘 안올 수도 있어 다른 예제를 하나 더 살펴보자.

 

 

위 예제의 경우 1,2,6,7 이라는 숫자를 옮겼을 때 최소이다.

 

 

 

 

잘 살펴보면, 움직이지 않는 숫자들은 모두 연속이라는 것을 파악할 수 있다.

 

그렇다면 왜 연속으로 이루어진 숫자들을 제외하고 나머지를 이동시켰을 때 최대인지 살펴보자.

 

 

 

위와같이 임의의 숫자들이 주어졌다고 가정하자.

 

 

이때 위와같이 연속으로 이루어진 부분수열이 있을 것이다 (파란색 네모)

 

 

 

그리고 z~z+2 까지 연속된 수열을 제외하고 나머지 숫자들은 저 수열보다 작거나 크다. 정확히 말하자면 z보다 작거나, z+2 보다 크다.

(중복된 숫자는 없기때문)

빨간색 네모의 숫자들은 z보다 작고, 초록색 네모의 숫자들이 z+2보다 크다고 가정하고 빨간네모를 좌측으로, 초록네모를 우측으로 움직인다면 다음과같이 될것이다.

 

 

 

 

즉, 연속된 부분수열을 제외한 나머지 숫자들은 크기에 맞추어서 좌측, 혹은 우측으로 배치한다면 연속된 부분수열은 따로 움직이지 않아도 결국 파란 네모처럼 중간에 오름차순으로 정렬되게 된다.

 

결론적으로 빨간네모와 초록네모의 개수만큼 움직임이 필요하고 그 움직임은 최소화해야 한다.

 

그말은 반대로 말하면 파란색 네모의 개수가 많을수록 최소의 움직임이 나온다는 뜻이다.

 

정리하자면, 주어진 수열에서 순차적으로 증가하는 부분수열중 가장 길이가 긴 수열의 원소개수가 k개라고 하고, 전체 개수를 n개라고 한다면 최소 이동수는 n-k이다.

 

결국 이 문제는 k를 구하는 문제이다.

 

다만 주의해야 할 점은 주어진 수열에서 순차적으로 증가하는 부분수열중 가장 길이가 긴 수열 에서 LIS 알고리즘처럼 단순히 이전 원소보다 증가만 한다고 되는것이 아니라 연속해서 증가해야한다.

 

1 2 3 4 5 는 가능 하지만

1 4 10 11 은 불가능 하다는 것이다.

 

 

구현

이제 위의 내용을 바탕으로 구현을 해보자.

 

우리는 연속하는 부분수열중 가장 긴 수열을 구해야한다. 그러므로 주어진 수열에서 연속하는 부분수열의 개수를 k개 라고 한다면 그 부분집합중 가장 선두의 숫자를 루트(root) 라고 부를것이다.

 

예를 들어 아래와 같은 수열이 주어진다면

 

 

아래와 같은 연속하는 부분수열들이 존재할 것이다. (같은 색이면 같은 부분수열에 속한다는 의미이다.)

 

그리고 3,6,9는 위에서 정의한 루트에 속한다.

 

따라서 모든 숫자는 선두이거나 선두가 아니다.

 

이를 구현하기 위해 

visited[] 배열과 counts[] 배열을 이용하였다.

visited[x] = x라는 숫자(x번째 인덱스의 숫자가 아니다) 를 이전에 방문했었는지

counts[x] = x라는 숫자(x번째 인덱스의 숫자가 아니다)  까지 이전에 연속한 숫자가 몇개 있었는지

를 뜻한다.

 

처음에 p라는 숫자를 볼때 루트인지 아닌지를 판단해야한다.

 

p라는 숫자가 루트이려면 p-1이라는 숫자를 이전에 방문하지 않았어야 하므로 visited[p-1] 이라는 값을 보면 알 수 있을 것이다.

 

1) 만약 p가 루트다.

먼저 visited[p] 를 방문상태로 체크하고,  counts[p] = 1 로 체크한다.

 

2) 만약 p가 루트가 아니다

역시 visited[p]를 방문상태로 체크하고, counts[p] = counts[p-1]+1 로 체크한다.

 

이런식으로 반복하다보면 최종적으로 counts[] 배열에는 왼쪽부터 시작해서 현재 자신까지 연속하는 숫자가 몇개인지 나타내는 숫자들이 들어있을 것이다. 따라서 해당 배열의 숫자중 가장 큰 값이 가장 긴 부분수열일 것이다.

 

 

C++ 구현 코드

#include <iostream>

using namespace std;

int n;
int arr[1000001];
int visited[1000001];
int counts[1000001];

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        visited[i] = -1;
        counts[i] = 0;
    }
    int now;
    for(int i=0;i<n;i++){ // 연속으로 증가하는 수열중 가장 길이 찾기
        now = arr[i];
        visited[now] = 1;
        if(now == 1){
            counts[now] = 1;
        }
        else{
            // 현재 숫자의 이전 숫자가 아직 발견되지 않은 상태
            if(visited[now-1] == -1){
                counts[now] = 1;
            }
            // 현재 숫자의 이전 숫자가 이전에 이미 발견된 상태
            else{
                counts[now] = counts[now-1] + 1;
            }
        }
    }
    int maxi = 0;
    for(int i=1;i<n+1;i++){
        if(counts[i] > maxi){
            maxi = counts[i];
        }
    }
    int ans = (n-maxi);
    cout << ans;
}