[백준/알고리즘] 10699 오늘 날짜, 2512 예산, 2805 나무 자르기, 이진 탐색, 파라메트릭 서치

[JS/ 오늘 날짜]

- 문제 번호 10699

let today = new Date();
console.log(today);
// 2024-08-16T06:12:39.184Z



// 현재 날짜와 시간을 가져오기
const currentDate = new Date();

// 각 구성 요소를 가져오기
const year = currentDate.getFullYear();
const month = currentDate.getMonth() + 1;
const day = currentDate.getDate();
const hours = currentDate.getHours();
const minutes = currentDate.getMinutes();
const seconds = currentDate.getSeconds();

// 날짜와 시간을 문자열로 포맷팅
const formattedDate = `${year}-${String(month).padStart(2, '0')}-${String(day).padStart(2, '0')}`;

// 포맷팅된 날짜와 시간을 출력
console.log(formattedDate); // 2024-08-16

 

- String.padStart(길이, 채울 문자) 사용해서 한 자리 숫자를 두 자리로 만들 수 있다.

---

[JS/ 예산]

- 문제 번호 2512

 

- 나의 방식

주어진 예산을 오름차순으로 정렬하고 모두 상한액을 배정한다고 가정하고 지방 수만큼 나눈다.

상한액을 나눈 값보다 가장 작은 예산이 작으면

전체 예산에서 가장 작은 예산 빼고 지방 수 - 1 해서 다시 나눈다.

 

아래는 내가 생각한 예시 입력값과 작성한 코드의 과정이다.

예를 들어

149 (주어진 예산)

28 29 30 31 32 (오름차순 정렬) > 하나씩 반복

149 / 5 = 29 ... 4     상한액이 28보다 크다.

(149 - 28) / 4 = 30 ... 1      상한액이 29보다 크다.

(149 - 28 - 29) / 3 = 30 ... 2      상한액이 30보다 크지 않다. 그런데 나머지가 2이다. 

(149 - 28 - 29 - 30) / 2 = 31      상한액이 31보다 크지 않다. 그런데 나머지가 0이다. 

 

상한액이 크지 않은 것 중에 나머지가 더 작은 거 선택한다.

31이 상한액일 때 나머지가 0이라서 최대로 예산 배정을 할 수 있다.

 

- 나의 코드

const input = require("fs").readFileSync("test.txt").toString().split("\n");
let regionNum = Number(input[0]);
let requiredBudget = input[1].trim().split(" ").map(Number);
let givenBudget = Number(input[2]);

let AscendingArr = requiredBudget.sort((a, b) => a - b);
// console.log(AscendingArr);

let totalBudget = requiredBudget.reduce((a, b) => a + b);
// console.log(totalBudget);

let answer = 0;
if (totalBudget <= givenBudget) {
  answer = AscendingArr[regionNum - 1];
} else {
  let remain = regionNum;
  for (let i = 0; i < regionNum; i++) {
    if (requiredBudget[i] < parseInt(givenBudget / (regionNum - i))) {
      givenBudget -= requiredBudget[i];
      answer = parseInt(givenBudget / (regionNum - i));
      // console.log("여기");
    } else if (requiredBudget[i] == parseInt(givenBudget / (regionNum - i))) {
      if (remain >= givenBudget % (regionNum - i)) {
        givenBudget -= requiredBudget[i];
        answer = parseInt(givenBudget / (regionNum - i));
      } else {
        break;
      }
    } else {
      // console.log("요기!");
      answer = parseInt(givenBudget / (regionNum - i));
      break;
    }
    // console.log(givenBudget);
  }
}
console.log(answer);

 

 

- 이진 탐색 (파라메트릭 서치) 이용한 방식

const input = require("fs").readFileSync("test.txt").toString().split("\n");
let n = Number(input[0].split(" ")[0]);
let arr = input[1].split(" ").map(Number);
let m = Number(input[2]);

// 이진 탐색을 위한 시작점과 끝점 설정
let start = 1;
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
while (start <= end) { // 이진 탐색 수행(반복문)
  let mid = parseInt((start + end) / 2); // 현재의 중간점(상한액)
  let total = 0;
  for (x of arr) { // 각 지방에서 요청한 예산 확인
    total += Math.min(mid, x); // 예산 배정
  }
  if (total <= m) { // 요청 만족 시, 상한액 증가
    result = mid;
    start = mid + 1;
  } else { // 조건 불만족 시, 상한액 감소
    end = mid - 1;
  }
}
console.log(result);

 

---

[JS/ 나무 자르기]

- 문제 번호 2805

 

- 나의 처음 코드 (시간 초과)

const input = require("fs").readFileSync("test.txt").toString().split("\n");
let [N, M] = input[0].split(" ").map(Number);
let treeArr = input[1]
  .trim()
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a);

let setHeight = 0;
if (treeArr[0] - M >= 0) {
  setHeight = treeArr[0] - M;
} else {
  setHeight = 0;
}

let totalCuts = M + 1;

while (totalCuts > M) {
  totalCuts = 0;
  for (let i = 0; i <= N; i++) {
    if (treeArr[i] - setHeight >= 0) {
      totalCuts += treeArr[i] - setHeight;
      if (totalCuts > M) break;
    }
  }
  if (totalCuts < M) break;
  setHeight++;
}
console.log(setHeight - 1);

 

- 시간 초과 원인

while 루프 내부의 for 루프에서 시간 초과가 나타날 수 있다. 이 방법은 큰 입력값에서 비효율적이며 시간 복잡도가 높음

 

- 힌트

• 입력 데이터의 크기와 범위가 크고 정해진 범위 내에서 최적의 해를 찾아야 함 > 이진 탐색을 통한 방법이 효과적
• 이진 탐색을 이용해서 setHeight를 찾자. 높이를 1씩 증가하는 대신, 높이의 범위 내에서 중간값을 선택하고 그 값으로 나무를 잘라본 후 필요한 나무 길이와 비교하는 방식으로 접근하기
• 중간값을 선택한다? 가능한 절단 높이의 범위에서 중간 값을 선택한다.
• 최소 높이는 0이고 최대 높이는 treeArr[0]이다. 이 범위에서 중간 값을 선택하고 자를 때 나무 길이 합이 M과 같거나 큰지 비교한다. 

- 개선한 코드 (통과)

const input = require("fs").readFileSync("test.txt").toString().split("\n");
let [N, M] = input[0].split(" ").map(Number);
// console.log(N, M); // 나무의 수, 필요한 나무 길이

let treeArr = input[1]
  .trim()
  .split(" ")
  .map(Number)
  .sort((a, b) => b - a);

let left = 0;
let right = treeArr[0];
let mid = 0;
let answer = 0;

while (left <= right) {
  mid = parseInt((left + right) / 2); // 임의로 설정
  totalCuts = 0;
  for (let i = 0; i < N; i++) {
    if (treeArr[i] - mid >= 0) {
      totalCuts += treeArr[i] - mid;
    }
  }
  if (totalCuts >= M) {
    answer = mid;
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
console.log(answer);

 

[주의할 점] 

while (left <= right) {

같을 경우도 while문을 돌려줘야 mid가 갱신되고 answer이 갱신된다. 

  if (totalCuts >= M) {
      answer = mid;

이 때, answer을 갱신해야 나무를 필요한 만큼 이상으로 자르는 경우가 될 수 있다. 

 

- 문제 해결 아이디어

이 문제를 봤을 때 절단기의 높이에 따라 얻을 수 있는 나무의 양이 달라지고 조건을 만족하는 최적의 값을 찾아야 한다. 

그리고 필요한 나무의 길이는 무려 최대 20억이다. > 파라메트릭 서치 이용

 

- 추가 정답 코드 (마찬가지로 이진 탐색)

const input = require("fs").readFileSync("test.txt").toString().split("\n");
let [n, m] = input[0].split(" ").map(Number);
let arr = input[1].split(" ").map(Number);

let start = 0;
let end = arr.reduce((a, b) => Math.max(a, b)); // 가장 큰 나무 길이

let result = 0;
while (start <= end) {
  // 이진 탐색 수행(반복문)
  let mid = parseInt((start + end) / 2);
  let total = 0;
  for (x of arr) if (x > mid) total += x - mid;
  if (total < m)
    end = mid - 1; // 나무의 양이 부족한 경우 더 많이 자르기 (높이 줄이기)
  else {
    result = mid; // 최대한 덜 잘랐을 때가 정답이므로, result에 기록
    start = mid + 1;
  }
}
console.log(result);