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

 

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

 

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

 

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

14002번: 가장 긴 증가하는 부분 수열 4

 

 

 

 

문제풀이 소감 🧑‍💻

 

LIS와 이분탐색을 이용해서 풀었다. DP와 LIS를 사용해서 O(N^2)으로도 풀리는 문제이기도 하다.

 

 

 

해결 전략 📝

 

https://bmy1320.tistory.com/entry/%EB%B0%B1%EC%A4%80-Gold-2-%EB%AC%B8%EC%A0%9C-%EB%B0%B1%EC%A4%80-Nodejs-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-12738-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-3-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-LIS

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

 

* 이전 풀이 내의 추가 풀이법을 참고해주세요.

 

 

 

 

주의 ❗

 

인덱스를 뒤에서부터 확인하는 이유는 다음과 같은 반례 때문입니다.

 

7
1 5 6 2 3 4 7

 

5와 2는 모두 LIS에서 인덱스 1의 위치를 부여받게 됩니다.

 

따라서 앞에서 부터 확인할 경우 LIS가 1 5 6 7 이 되어버리게 되어 틀립니다.

 

뒤에서 부터 확인해야지 1 2 3 4 7로 올바른 LIS가 나오게 됩니다.

 

 

 

 

 

정답 💯

 

 

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

const [input_N, input_nums] = input.map((v) => v.split(" ").map(Number));

function solution(N, nums) {
  const binarySearch = (target, left, right) => {
    while (left < right) {
      let 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 result = [];
  const LIS = [nums[0]];

  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 changePlace = binarySearch(nums[i], 0, LIS.length - 1);
      place[i][1] = changePlace;
      LIS[changePlace] = nums[i];
    }
  }

  if (LIS.length === 0) {
    console.log(0);
    return;
  }

  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;
    }
  }

  console.log(result.length);
  console.log(result.reverse().join(" "));
}

solution(input_N, input_nums);