백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1365 꼬인 전깃줄

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1365 꼬인 전깃줄

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

1365번: 꼬인 전깃줄

 

 

문제풀이 소감 🧑‍💻

기본적인 LIS 문제 같다.

 

특별한 반례없이 잘 풀린다.

 

 

요구사항 📋

• 꼬인 전깃줄들이 주어진다.
• 최소한으로 전깃줄을 삭제하여 꼬인 상태를 풀어라.
• 삭제한 전깃줄 갯수를 출력한다.

 

해결 전략 📝

 

최소한으로 꼬인 전깃줄을 삭제하라는 말은 최대한 꼬이지 않은 전깃줄들을 남기라는 말과 같다.

 

즉, 최대 증가 부분 수열을 구해서 전체 갯수에서 뺀 값을 구하라는 것이다.

 

결국 이 문제는 LIS 문제가 된다.

 

 

주어진 배열에서 최장 증가 부분 수열을 구하고 전체 길이에서 빼면 된다.

 

 

 

• LIS라는 빈 배열을 만들어준다.
• 주어진 숫자들을 앞에서부터 하나씩 탐색한다.
• LIS가 비어 있거나 LIS끝 값이 현재 숫자보다 작다면 LIS에 현재 숫자를 추가해준다.
• 만약 LIS 끝 값이 현재 숫자보다 크다면 LIS 내부로 숫자를 넣어줘야한다.
• 어느 위치에 넣어야하는지 인덱스를 알아야 하기 때문에 이분 탐색을 실행해준다.
• 나온 위치에 현재 숫자를 대입한다.
•  전체 N에서 최종적으로 만들어진 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) {
      const mid = ~~((left + right) / 2);
      if (LIS[mid] < target) left = mid + 1;
      else right = mid;
    }

    return right;
  };

  const LIS = [];
  nums.forEach((num) => {
    if (LIS.length === 0 || LIS[LIS.length - 1] < num) LIS.push(num);
    else {
      const changePlace = binarySearch(num, 0, N - 1);
      LIS[changePlace] = num;
    }
  });

  return N - LIS.length;
}

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