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

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

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

14003번: 가장 긴 증가하는 부분 수열 5

 

 

문제풀이 소감 🧑‍💻

이분탐색 + LIS 문제.

가장 긴 증가하는 부분 수열 시리즈 문제를 쭉 풀어온게 도움이 되었다.

 

가장 긴 증가하는 부분 수열 시리즈 문제 4 에서 최종 수열을 만들때 앞에서 부터 확인하는 것이 아닌 뒤에서부터 확인하는 이유에 대해서 시행착오를 겪어가면서 푼 덕분에 이번 문제는 틀리지 않고 통과하였다.

 

 

 

주의 ❗

최종 수열 형태는 place 배열의 뒤에서부터 확인하면서 만들어야 한다.

 

7
1 5 6 2 3 4 7

 

위의 반례에 주의

 

최종 수열은 1 2 3 4 7 이 나와야한다.

 

앞에서 부터 확인하면 1 5 6 4 7 이라는 이상한 배열로 만들어지게 된다.

 

 

 

왜일까?

 

[ [ 1, 0 ], [ 5, 1 ], [ 6, 2 ], [ 2, 1 ], [ 3, 2 ], [ 4, 3 ], [ 7, 4 ] ]

 

만들어진 place 배열이다.

 

앞에서 부터 인덱스를 맞춰가면

 

확인 => [ [ 1, 0 ], [ 5, 1 ], [ 6, 2 ], [ 2, 1 ], [ 3, 2 ], [ 4, 3 ], [ 7, 4 ] ]

 

 

result = [ 1, 5, 6 ,4 ,7 ] 

이 만들어지게 된다.

 

이유는 5,6 과 2 3 의 인덱스가 겹치기 때문.

 

4가 하필 또 인덱스가 3이기때문에 6 다음 4가 나온다고 착각하는 것이다.

 

앞에서 부터 처음 만나는 인덱스를 값으로 생성하는 해결법의 반례이다.

 

이것을 올바르게 고치기 위해서는 배열을 거꾸로 확인해가면된다.

 

[ [ 1, 0 ], [ 5, 1 ], [ 6, 2 ], [ 2, 1 ], [ 3, 2 ], [ 4, 3 ], [ 7, 4 ] ]  <= 확인

 

이렇게 뒤에서부터 인덱스 4 3 2 1 0 을 찾아가면서 탐색해야지 올바른 결과값이 나오게 된다.

(result는 거꾸로 들어있을테니 reverse 를 해준다.)

 

result = [ 1, 2, 3 ,4 ,7 ] 

 

 

해결 전략 📝

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 ]

 

 

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

 

 

 

 

정답 💯

 

 

 

const { exit } = require("process");

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

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

function solution(N, portnumbers) {
  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]);
  const LIS = [];
  const result = [];
  portnumbers.forEach((portnumber, idx) => {
    place[idx][0] = portnumber;
    if (LIS.length === 0 || LIS[LIS.length - 1] < portnumber) {
      LIS.push(portnumber);
      place[idx][1] = LIS.length - 1;
    } else {
      const changePlace = binarySearch(portnumber, 0, N - 1);
      place[idx][1] = changePlace;
      LIS[changePlace] = portnumber;
    }
  });

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

  let inclusion = LIS.length - 1;
  place.reverse().forEach((target) => {
    if (target[1] === inclusion) {
      result.push(target[0]);
      inclusion -= 1;
    }
  });

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

solution(input_N, input_portnumbers);