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

문제 설명 : https://www.acmicpc.net/problem/14003

 

문제 요약 :

1. 수열 A에 대해 가장 긴 증가하는 부분 수열 구하기
2. 수열의 길이와 수열을 출력

문제 풀이 시간 : 1시간

문제 성공 여부 : 실패

 

 

접근 방법(성공) :

1. 이전 수열 중 가장 긴 수열(마지막 값이 현재 인덱스값보다 작은 수열)의 길이(idx)에 대해 그 최솟값을 저장하는 dp 배열 (수열의 길이)
2. 각 인덱스 별 자식의 수 저장 배열 (역추적)

 

[10 20 8 30] 이라는 배열이 있다.

각각의 인덱스에 대해 이전 수열 중 가장 긴 수열의 길이를 찾아보자

 

10은 본인보다 작은 수가 없으므로 0

20은 10이 본인보다 작기에 1

8은 본인보다 작은 수가 없으므로 0

30은 20이 본인보다 작기에 2가 된다.

 

여기서 주목해야 할 부분은 "30보다 작은 수열 중 가장 긴 수열의 길이를 어떻게 찾을까?"이다

 

특정 인덱스(i) 이전에 있는 수열 중, 모든 값들이 A[i]값 보다 작은 가장 긴 수열의 길이를 편의상 t값이라고 하겠다.

 

가장 기본적인 방법은 30보다 작은 모든 수에 대해 비교를 해보는 것이다.

8은 t값이 0이기에 1개

20은 t값이 1이기에 2개

10은 t값이 0이기에 1개

 

이렇게 모든 인덱스를 다 뒤져봐야 [...20 30]으로 오는 수열이 가장 긴 수열임을 알 수 있다.

 

하지만 100만 개의 수열에 대해 모두 이러한 과정을 거칠 수는 없다.

조금 더 이전의 값들을 활용해서 쓸모없는 계산을 줄여야 한다.

 

조금 더 효율적으로 30의 t값을 찾는 방법이 뭘까?

 

 

그건 바로 t값이 가장 큰 수부터 비교를 수행하는 것이다.

 

t값이 1인 20과 현재값 30을 비교해 보고,

30이 더 크다면 다른 수들은 비교를 할 필요가 없어진다! (...20 의 수열이 가장 길었기 때문이다.)

 

 

하지만, 이 방식에도 문제점이 존재한다.

 

문제점 1

30이 아니라 0이었다면?

가장 t값이 큰 20부터 10, 8까지 모든 t값들을 확인하며 내려가야 한다..

 

문제점 2

똑같은 t값에 대해 비교를 하는 것도 매우 비효율적이다.

10과 8은 모두 t값이 0으로 사실 8만 비교해도 되기 때문이다.

 

 

자 거의 다 왔다. 

문제점 1과 문제점 2를 해결할 좋은 방법이 무엇일까?

 

문제점 1은 모든 t값을 일일이 다 비교하는 것이 문제였다.

우린 현재 값보다 작으면서 가장 t값이 큰 인덱스만 찾으면 되므로, 이진탐색을 사용할 수 있다!

 

문제점 2는 같은 t값에 대해서는 최솟값만 저장함으로써 불필요한 연산을 줄일 수 있다.

10 8 6 5 12 <- 이경우 10~5까지의 t값은 0으로 모두 같으므로 5와 12만 비교하면 된다!

 

 

결론

현재 인덱스에 대해 t값을 찾는 방법은 다음과 같다.

 

t값에 대해 가장 작은 수를 저장하는 dp 배열 선언

 

t값이 0, 1, 2, 3,... 인 값들 중에서 가장 작은 값들을 최신화하는 것이다!

 

이렇게 하면 현재 인덱스에 대해 dp 배열에 이진탐색으로 t값을 알 수 있고, t값에 대한 최솟값을 갱신해갈 수 있다.

 

7
10 20 5 10 40 15 50

dp = [5, 10, 15, 50]

 

 

이렇게 가장 긴 증가하는 수열의 길이와 수열을 구했다고 생각하였지만 반례가 존재하였다. ㅠ ㅠ ㅠ ㅠ 푼 줄 알았는데 ㅠ ㅠ

 

반례

6
5 10 2 15 13 6

dp = [2, 6, 13]

 

길이는 3이 맞지만, 지금 dp 배열을 보면 6 이전에 있는 13이 더 뒤에 있는 것을 볼 수 있다.

 

그렇다. dp 배열은 t값에 대해 가장 작은 수를 저장하는 배열이기 때문에 순서가 역전될 수 있었다.

 

따라서, 하나의 배열이 더 필요하다고 판단하였다.

 

각 인덱스 별 t값을 저장하자

바로 위의 예시는 아래와 같이 된다.

arr = [0 1 0 2 2 1]

 

가장 긴 수열의 길이가 3이므로, 배열의 가장 뒤에서부터 t값이 2인 수를 찾는다.

4번째 인덱스인 13을 찾았으면 t값이 1인 수를 찾는다.

1번째 인덱스인 10을 찾았으면 t값이 0인 수를 찾는다.

0번째 인덱스인 5를 찾았으면 모든 수열을 찾았으므로, reverse 하면 가장 긴 증가하는 부분 수열을 찾을 수 있다!

 

전체 코드(성공) :

const solution = () => {
  const fs = require("fs");
  const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
  const input = fs.readFileSync(filePath).toString().split("\n");
  const N = Number(input[0]);
  const A = input[1].split(" ").map(Number);

  const dp = [A[0]]; // lowerCnt 별 가장 작은 수
  const lowerCnt = [0]; // 본인 이전의 가장 긴 수열의 길이
  for (let i = 1; i < N; i++) {
    const idx = findIdx(A[i], dp); // A[i]가 들어갈 위치를 반환받는다.

	// A[i]가 현재 lowerCnt보다 더 커진 경우 그냥 추가하고, 아닐 경우 해당 인덱스의 최소값을 갱신
    dp[idx] = idx === dp.length ? A[i] : Math.min(dp[idx], A[i]); 
    
    lowerCnt[i] = idx; // 해당 숫자의 lowerCnt
  }

  let len = dp.length; // 수열의 길이
  let answer = len + "\n"; 

  // 역추적
  let order = [];
  for (let i = N - 1; i >= 0; i--) {
    if (lowerCnt[i] === len - 1) {
      order.push(A[i]);
      len--;
    }
  }

  answer += order.reverse().join(" ");
  return answer;
};

const findIdx = (num, arr) => {
  let left = 0;
  let right = arr.length - 1;

  let idx = 0;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (num > arr[mid]) {
      // num이 더 클 경우 오른쪽 영역을 탐색
      left = mid + 1;
      idx = left;
    } else {
      // num이 작거나 같을 경우 왼쪽 영역을 탐색
      right = mid - 1;
    }
  }
  return idx;
};

const answer = solution();
console.log(answer);

 

 

내가 문제를 풀 때의 의식의 흐름대로 최대한 쉽게 설명하려 했으나...

막상 쓰고 나니 이해하기 쉽지 않을 것 같다.. ㅠㅠ