백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 2565 전깃줄 [LIS]

백준/ Gold 5 문제 , 백준 Node.js 자바스크립트 2565 전깃줄 [LIS]

 

 

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

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

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

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

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

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

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

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


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

 

 

 

문제 출처 🏠

 

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

2565번: 전깃줄

 

 

문제풀이 소감 🧑‍💻

이 문제를 보고 LIS 문제라는 것을 떠올리는 게 핵심인 것 같다.

N이 100까지라 굳이 LIS 를 사용하지 않아도 되지만, LIS 연습하기에 적절한 문제이다.

 

 

요구사항 📋

전깃줄이 교차하는 것이 없도록 최소한의 전깃줄만 삭제하고 삭제한 개수를 출력하시오.

 

 

해결 전략 📝

우선, 교차하는 것이 없어지는 조건을 확인하기 위해

 

입력받은 전깃줄 연결 위치 리스트들의 첫번째 값들을 기준으로 오름차순 정렬을 해준다.

 

1번 전깃줄부터 차례대로 확인하는 것인데, 교차하는 것이 없어지는 조건은 자신보다 순번이 낮은 전깃줄들 중 자신이 연결한 전깃줄의 도착위치보다 높은 위치에 도착하는 전깃줄이 없어야한다.

 

이점을 확인해보면 결국 정렬한 리스트들의 최장 증가 부분 수열의 크기가 곧 남겨야하는 전깃줄의 최대 갯수 라는 것을 알 수 있다. 

 

삭제할 전깃줄의 최솟값을 찾아야하는 것이 정답이므로 전체 N에서 최장 증가 부분 수열 크기를 빼주면 된다. 

 

그 값이 없애야할 전깃줄의 개수이기 때문이다.

 

 

주어진 N 크기의 record 배열을 0으로 모두 초기화한다.

 

전깃줄의 정보가 담긴 codes 를 순회하면서 record에 값을 저장해 나아가면 된다.

 

 

순회를 마치면 최종적으로 record에는 아래와 같은 값이 담겨있고, 이 값들 중 가장 큰 값인 5가 LIS 값이다.

 

1, 1, 2, 1, 2, 3, 4, 5

 

이 5가 뜻하는 것은 남겨야할 전깃줄의 최대 갯수이고 , 전체 크기에서 5 를 뺀 3이 바로 없애야할 전깃줄의 갯수이다.

 

 

정답 💯

 

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

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

function solution(N, codes) {
  const record = Array.from({ length: N }).fill(0);
  codes = codes.sort((a, b) => a[0] - b[0]);
  codes.forEach((_, idx) => {
    for (let j = 0; j < idx; j++) {
      if (codes[j][1] < codes[idx][1] && record[idx] < record[j]) {
        record[idx] = record[j];
      }
    }
    record[idx] += 1;
  });
  return N - Math.max(...record);
}

console.log(solution(Number(input_N), input_codes));