[백준][#2631] 줄세우기 - JavaScript

문제 설명

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

[예제 입력 1]

7
3
7
5
2
6
1
4

[예제 출력 1]

4

풀이

위의 예제 입력 1을 예시로 든다면 처음에는 다음과 같은 모습일 것이다.

해당 문제에서는 아무 곳이나 아이들을 넣을 수 있기 때문에 전체 중에서 가장 길게 부분적으로나 연속적으로 큰 번호를 가진 아이들을 기준으로 삼으면 된다. 그렇게되면 나머지 인원만 옮기는 것이 최소한의 이동으로 원하는 결과를 얻을 수 있을 것이다.

전체 중에서 가장 길게 부분적으로나 연속적으로 큰 번호를 가진 아이들을 기준

기준을 잡기 위해서는 LIS 알고리즘을 활용하면 된다.
위의 예시에서 LIS를 이용하면 3, 5, 6의 길이인 3을 얻을 수 있다. 그렇다면 나머지 인원인 4명만 옮기면 최소한의 이동으로 오름차순으로 정렬 할 수 있게 된다.

// N은 아이들의 수
// data = [3, 7, 5, 2, 6, 1, 4] 아이들의 번호
for (let i = 1; i < N; i++) {
  dp[i] = 1;
  for (let j = 0; j < i; j++) {
    if (data[i] > data[j] && dp[i] < dp[j] + 1) {
      dp[i] = dp[j] + 1;
    }
  }
  if (maxLength < dp[i]) maxLength = dp[i];
}

위의 코드에서 사용된 dp배열에 저장되는 값들은 각 인덱스에서의 부분적으로나 연속적으로 큰 번호를 가진 아이들의 인원 수이다.

data = [3, 7, 5, 2, 6, 1, 4] 아이들의 번호
예를 들면 i = 2일 때(5번 아이), dp[2]가 가지게 되는 값은 2명(3번 아이, 5번 아이)이다.

if 조건문에 사용되는 두 조건

1. data[i] > data[j]

LIS 알고리즘은 증가하는 값을 성립해야 하기 때문에 i값과 i의 이전 값들인 j를 비교하여 작은지 확인하는 조건이다.

2. dp[i] < dp[j] + 1

단순히 1번 조건인 작은지만 확인하게 되면 원하는 결과를 가질 수 없다.

data = [3, 7, 5, 2, 6, 1, 4] 아이들의 번호
예를 들면 i = 4일 때(6번 아이), dp[4]가 가지게 되는 값 4명(3번 아이, 5번아이, 2번 아이, 6번 아이)이다.

2번 아이는 부분적으로나 연속적으로 큰 번호가 아니다.

위의 같은 상황을 제외시켜주어야 하기 때문에 dp[i] < dp[j] + 1조건이 추가가 된 것이다.

dp배열이 가지는 값의 의미를 다시 생각해보며 dp[i=4] < dp[j=3] + 1의 경우를 보면,

dp[3] = 1명(2번 아이)의 값을 가지고 있을 것이고 dp[4] = 현재 3명(3번 아이, 5번 아이, 6번 아이)를 가지고 있기 때문에 dp[3]의 경우에다 6번 아이를 추가했을 때의 값과 현재 dp[4] 값을 비교하여 추가했을 때의 값이 커질 때만 아이를 추가해주면 된다.

기준을 잡고난 뒤

기준을 잡았더라면 전체 인원수에서 기준 잡은 인원수(전체 인원수 - dp배열 중 가장 큰 값)를 빼주면 결과 값을 얻을 수 있게 된다.

최종 코드

const solution = (N, data) => {
    const dp = new Array(N).fill(0);
    let maxLength = 0;

    for (let i = 0; i < N; i++) {
        dp[i] = 1; // 자신은 포함되어 있어야 하기 때문에 
        for (let j = 0; j < i; j++) {
            if (data[i] > data[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (maxLength < dp[i]) maxLength = dp[i];
    }

    // answer
    console.log(N - maxLength);
};

const fs = require('fs');

const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input[0];
const data = [];
for (let i = 1; i <= N; i++) {
    data.push(+input[i]);
}

solution(N, data);