[BaekJoon] 3745 번 오름세 문제 - (nodejs)

문제 번호 :  3745 번

문제 바로가기 ☞ https://www.acmicpc.net/problem/3745

---

 

<<< 문제 내용 >>>

---

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

for (let i = 0; i < input.length; i += 2) {
  let N = input[i]; // 안씀

  let array = input[i + 1].trim().split(/\s+/g).map(Number);
  let temp = [];

  // lower bound. 그러나 이 코드는 모든 값이 중복인 경우 하나씩 확인해야하는 단점이 있다.
  // 목표 값이 작은 경우만 고려하고, 크거나 같을 때는 high를 mid로 변경하는 방식이
  // 더 효율적이다.
  const lower_bound = (target, array) => {
    let low = 0;
    let high = array.length - 1;

    while (low <= high) {
      let mid = Math.floor((low + high) / 2);

      if (array[mid] === target) {
        while (array[mid] === target) mid--;

        return mid + 1;
      }

      if (array[mid] < target) low = mid + 1;
      else high = mid - 1;
    }

    return low;
  };

  array.forEach((el) => {
    if (el > (temp[temp.length - 1] || 0)) {
      // 이번 값이 전 값 보다 클때
      temp.push(el);
    } else {
      // temp 값 중에 바꿔줄 수 있는 값 찾기
      let location = lower_bound(el, temp);
      temp[location] = el;
    }
  });

  console.log(temp.length);
}

 

 

도움이 되셨다면 공감 부탁드립니다.