백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 2550 전구 [ 이분탐색, LIS ]

백준/ Gold 3 문제 , 백준 Node.js 자바스크립트 2550 전구 [ 이분탐색, LIS ]

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

 

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

2550번: 전구

 

 

 

문제풀이 소감 🧑‍💻

 

꼬인 선들을 제거하고 가장 많은 선들을 이을 수 있는 경우를 찾는 것이라면 LIS를 구하는 문제이다.

 

주어진 숫자들의 위치를 잘 생각해서 풀어보면 다른 LIS문제들과 동일하게 풀 수 있다.

 

 

요구사항 📋

• 첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다.
• 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.
• 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.
• 첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다.
• 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다.
• 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

 

 

해결 전략 📝

어떤 부분의 LIS를 구해야할지 생각해보자.

 

주어진 전구쪽에 있는 숫자들이 Key 값이라고 생각하고, 스위치쪽에 주어진 숫자들의 인덱스가 Value 값이라고 생각하면 된다.

 

5
2 4 1 5 3
4 5 1 3 2

 

예시를 보면 

 

4 5 1 3 2 가 Key 값으로 넣어줄 배열

 

2 4 1 5 3의 각 값들의 인덱스를 Value로 넣어줄 것이다.

 

 

최종적으로

 

'2' : 0

'4' : 1

'1' : 2

'5' : 3

'3' : 4

 

이렇게 될것이다.

 

 

이제 이 Value값들을 4 5 1 3 2 에 맞춰 넣어주면 1 3 2 4 0 이 된다.

 

여기서의 LIS를 구해 주면 1 2 4  가 나오는데,

 

이 1 2 4 가 뜻하는 것은 스위치 배열에서의 인덱스이다.

 

즉, 스위치 배열에서의 1, 2, 4 번 인덱스에 해당 하는 값들만이 허용되는 값이다.

 

따라서 인덱스 1, 2, 4의 값 [4, 1, 3] 의 값을 맞게 출력해주면 된다.

 

 

 

정답 💯

 

 

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

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

function solution(N, switches, lights) {
  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]);
  const dict = {};
  const position = [];
  const LIS = [];
  const result = [];
  switches.forEach((Switch, idx) => (dict[Switch] = idx));
  lights.forEach((light) => position.push(dict[light]));

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

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

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

solution(input_N, input_switches, input_lights);