백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12014 주식 [ 이분탐색, LIS ]

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12014 주식 [ 이분탐색, LIS ]

 

 

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

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

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

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

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

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

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

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


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

 

 

문제 출처 🏠

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

12014번: 주식

 

 

요구사항 📋

• 입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
• 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다.
• 각 테스트 케이스의 첫 줄에 두 정수 N과 K이 주어진다.
• N은 앞으로 주가를 알 수 있는 날 수이며, (1 ≤ N ≤ 10,000) K는 거래의 회수이다. (1 ≤ K ≤ 10,000)
• 다음 줄에는 앞으로 N 날의 주가가 사이에 공백을 두고 주어진다.
• 주가는 1부터 10,000 사이의 정수이다.

 

• 각 테스트 케이스에 대해서 출력은 한 줄로 구성된다.
• T 번째 테스트 케이스에 대해서는 첫째 줄에는 "Case #T"를 출력한다.
• 두 번째 줄에는 주어진 조건을 만족하게 주식을 살 수 있으면 1, 아니면 0을 출력한다.

 

 

해결 전략 📝

 

• LIS라는 빈 배열을 만들어준다.
• 주어진 숫자들을 앞에서부터 하나씩 탐색한다.
• LIS가 비어 있거나 LIS끝 값이 현재 숫자보다 작다면 LIS에 현재 숫자를 추가해준다.
• 만약 LIS 끝 값이 현재 숫자보다 크다면 LIS 내부로 숫자를 넣어줘야한다.
• 어느 위치에 넣어야하는지 인덱스를 알아야 하기 때문에 이분 탐색을 실행해준다.
• 나온 위치에 현재 숫자를 대입한다.
• 최종적으로 만들어진 LIS의 길이가 K와 같거나 큰지 확인한다.
• K와 같거나 크다면 1, 작다면 0을 출력한다.

 

 

 

 

정답 💯

 

 

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

const input_T = Number(input[0]);
input.shift();
const input_TC = input.map((v) => v.split(" ").map(Number));

function solution(T, TC) {
  for (let Case = 1; Case <= T; Case++) {
    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 [_, K] = TC[2 * Case - 2];
    const nums = TC[2 * Case - 1];
    const LIS = [];

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

    console.log(`Case #${Case}`);
    console.log(LIS.length >= K ? 1 : 0);
  }
}

solution(input_T, input_TC);