백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12738 가장 긴 증가하는 부분 수열 3 [ 이분 탐색, LIS ]

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12738 가장 긴 증가하는 부분 수열 3 [ 이분 탐색, LIS  ]

 

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

 

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

12738번: 가장 긴 증가하는 부분 수열 3

 

 

문제풀이 소감 🧑‍💻

 

이분 탐색은 세그먼트 트리 풀때 많이 사용했었는데, LIS 문제에 적용할 생각을 처음에 못했다.

 

파이썬은 보통 bisect이라는 라이브러리를 사용하면 되지만 JS는 그런건 존재하지 않기 때문에 직접 구현해야한다.

 

사실 큰 위치만 찾으면되서 이분 탐색 구현이 어렵지는 않다.

 

 

요구사항 📋

• 주어진 숫자들 중에서 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

주의 ❗

가장 긴 증가하는 부분 수열 시리즈의 요구사항은 간단하지만, 난이도 차이는 크기 범위에 따라 극명하게 갈린다.

 

이번 문제는 N (1 ≤ N ≤ 1,000,000) 이므로 일반적인 dp 를 사용해서 O(n^2) 시간복잡도로는 풀 수 없다.

 

 

 

해결 전략 📝

 

접근법 자체는 간단하다.

 

• LIS 배열에 숫자 처음 값을 넣고 시작한다.
• LIS 배열 끝자리 숫자보다 큰 숫자가 나오면 LIS 배열에 큰 숫자를 스택에 담듯이 넣어준다.
• 이때, LIS 배열의 어느 위치에 담겨있는지를 표시해주기 위해 place라는 배열을 따로 선언하여 배열 위치를 담아준다.
• 만약, LIS 배열 끝자리 숫자보다 작은 값이 나온다면, LIS 배열 어느 위치에 넣어줘야 하는지를 판단해줘야한다.
• 이때 이분탐색을 사용한다. 
• LIS 양쪽 끝 인덱스를 넣어준 뒤 LIS 배열에서 자신보다 큰값이 처음으로 나오는 위치에 값을 넣어준다.
• 이 위치를 return 하여 place배열에도 표시해준다.
• 모든 순회를 마치게 되면 각 place배열에 각 숫자들의 LIS 배열에서 어느 위치에 할당되어있는지 표시되어있을 것이다.
• 우리가 필요한 것은 가장 긴 수열 값의 길이이므로 place 배열에서 각 요소들의 1번째 값들 중 가장 큰 값을 출력해주면된다.

 

 

+)

• 사실 길이만 출력해주면 되어서 굳이 가장 긴 부분 수열까지 찾아내줄 필요는 없었지만, 이후 시리즈 문제들도 해결하는데 도움이 되기 때문에 추가적인 풀이를 작성하였다.
• 만약, 이 문제만 해결할 것이면 그냥 위 과정까지만 수행하면된다. 
• place 배열을 뒤에서부터 순회하면서 결과값을 그냥 담아주기만 하면된다.
• 이때, 한번 나온 위치는 뒤에 또 나오더라도 담아주지 않으며 순서를 지켜가면서 넣어준다.

 

 

 

 

ex)

 

1,2,4,5,3,4,2,5,6 이라면

 

1, 2, 4, 5, 3, 4, 2, 5, 6  <-

 

파란 부분에 해당하는 숫자들만 결과값에 넣어준다.

 

 

이 과정까지 수행해서 만들어진 결과값에 담긴 숫자들이 가장 긴 증가 수열이다.

 

이 접근법으로 이후 가장 긴 증가 수열 시리즈 문제들도 해결하는데 도움이 될 것이다.

 

 

 

 

이해를 돕기 위해 추가 설명을 좀 더 해보겠다.

 

6
10 20 10 30 20 50

 

예시를 입력하여 코드를 실행하면 for 문이 다 끝난 시점에서 place는 이 상태이다.

 

[ [ 10, 0 ], [ 20, 1 ], [ 10, 0 ], [ 30, 2 ], [ 20, 1 ], [ 50, 3 ] ]

 

각 요소의 0번째 인덱스는 숫자가 담겨있고

1번째 인덱스에는 LIS내의 위치들이 담겨있다.

 

 

우리는 뒤에서부터 이제 가장 긴 증가수열을 만들어가면된다.

 

현재 필요한 인덱스 3

 

우선 처음 값인 50을 넣어준다. 

 

LIS = [ 50 ]

 

다음 필요한  인덱스 2

 

이후 20으로 넘어가면 인덱스가 1이므로 넣어줄 수 없다.

 

이후 30은 인덱스가 2이므로 넣어줄 수 있다.

 

LIS = [ 50 , 30 ]

 

다음 필요한  인덱스 1 

 

이후 10은 인덱스가 0이므로 넣어줄 수 없다.

 

이후 20은 인덱스가 1이므로 넣어줄 수 있다.

 

LIS = LIS = [ 50, 30, 20 ]

 

다음 필요한  인덱스 0

 

이후 10은 인덱스가 0이므로 넣어줄 수 있다.

 

 

최종적으로 만들어진 LIS 는 LIS = [ 50, 30, 20, 10 ] 이다.

 

길이를 출력하는 것이므로 여기서 길이만 출력해주면된다.

 

만약 수열의 요소값들을 원한다면 reverse 해서 출력해주면 된다.

 

 

 

 

 

 

정답 💯

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

const input_N = Number(input[0]);
input.shift();
const input_nums = input[0].split(" ").map(Number);

function solution(N, nums) {
  const binarySearch = (target, left, right) => {
    while (left < right) {
      const mid = ~~((left + right) / 2);
      if (LIS[mid] < target) left = mid + 1;
      else right = mid;
    }

    return right;
  };

  const place = Array.from({ length: N }, () => [0, 0]).fill([nums[0], 0], 0, 1);
  const LIS = [nums[0]];
  const result = [];

  for (let i = 1; i < N; i++) {
    place[i][0] = nums[i];
    if (LIS[LIS.length - 1] < nums[i]) {
      place[i][1] = LIS.length;
      LIS.push(nums[i]);
    } else {
      const exchangePlace = binarySearch(nums[i], 0, LIS.length - 1);
      place[i][1] = exchangePlace;
      LIS[exchangePlace] = nums[i];
    }
  }
  if (LIS.length === 0) return 0;

  let inclusion = LIS.length - 1;
  for (let i = N - 1; i >= 0; i--) {
    if (inclusion === place[i][1]) {
      result.push(place[i][0]);
      inclusion -= 1;
    }
  }

  return result.length;
}

console.log(solution(input_N, input_nums));