알고리즘 오답노트 정리

결혼식

let num = 5;
let arr = [
  [14, 18],
  [12, 15],
  [15, 20],
  [20, 30],
  [5, 16],
];

let answer = Number.MIN_SAFE_INTEGER;

let T_arr = [];

for (let el of arr) {
  T_arr.push([el[0], "s"]);
  T_arr.push([el[1], "e"]);
}

T_arr.sort((a, b) => {
  if (a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt(); // 기억할 것
  else return a[0] - b[0];
});
let cnt = 0;

for (let el of T_arr) {
  if (el[1] === "s") cnt++;
  else cnt--;

  answer = Math.max(answer, cnt);
}
console.log(answer);

같은 시간내에 최대 인원을 구하는 문제이다. 어려운 점은, unicode로 알파벳을 변경하여서 사용한 방법이었다.
나는 숫자로 사용하는 것이 더 좋았겠다고 생각했지만,
그래도 문자로 사용해서 해보는 것도 해보았다.

charCodeAt()을 쓰면 유니코드로 바뀐다 알파벳 기준으로 먼저오는 알파벳이 더 숫자가 작다 이를 통해 정리하여서 입장과 퇴장을 구분해서 처리하는 것이 좋았다.

이분 검색

let arr = [23, 87, 65, 12, 57, 32, 99, 81];
let lt = 0;
let rt = arr.length - 1;
let target = 32;
arr.sort((a, b) => a - b);

while (lt <= rt) {
  let mid = parseInt((lt + rt) / 2);
  if (arr[mid] === target) {
    console.log(mid + 1);
    break;
  } else if (arr[mid] > target) {
    rt = mid - 1;
  } else {
    lt = mid + 1;
  }
}

이분 검색이란 간단히 말하면 반으로 쪼갠다는 뜻이다.
그 중간값을 통해 방향을 잡는 방법이다.

좋은 방법이고, 기억해야할 것 같아서 적었다.

뮤직비디오

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let num = 3;

function count(arr, mid) {
  let cnt = 1;
  let sum = 0;

  for (let x of arr) {
    if (sum + x > mid) {
      //더하기전에 확인함
      cnt++;
      sum = x;
    } else {
      sum += x;
    }
  }

  return cnt;
}

function solution(arr, m) {
  let answer = 0;
  let lt = Math.max(...arr);
  let rt = arr.reduce((a, b) => a + b, 0);
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (count(arr, mid) <= m) {
      answer = mid;
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }

  return answer;
}

console.log(solution(arr, num));

//많은 장수가 나온다는 것은 시간이 너무 적어서 늘려ㅑ줘야함
//적은 장수가 나온다는 것은 시간이 너무 많아서 줄여줘야함

//parameter, argument 오류로 고생함

//함수 두개로 나눠 푸는거 기억할 것

여러 어려운 점 중에 기억나는 것은 로직을 간단히 하기 위해서 함수별로 푸는 방법을 사용한 것이 좋았다. 둘을 엮어서 하는 것보다 각각 분업을 시켜서 처리하는 방식이 더 간단한데 이를 직접 보여주는 문제였다.

또한 count같은 변수명을 겹쳐서 사용하였다. 확실히 겹치는 변수명은 피해주어야한다.
이 때문에 고생했는데 네이밍에 대해 다시 상기할 수 있었다.

마구간 정하기

let horse = [1, 2, 8, 4, 9];

let count = 3;
horse.sort((a, b) => a - b);
let lt = 1;
let rt = horse[horse.length - 1];
let answer = 0;
while (lt <= rt) {
  let mid = parseInt((lt + rt) / 2); //사거리를 의미함
  if (checking(horse, mid) >= count) {
    //만약에 4마리면, 거리를 늘려줘야하고,
    //3마리인 경우에는 늘려줘야함 최대거리라서
    //만약에 2마리면, 거리를 줄여야한다.
    //목표는 3마리의 말을 배치해야하고,
    //거리가 최대어야함

    answer = mid;
    lt = mid + 1;
  } else {
    rt = mid - 1;
  }
}
console.log(answer);

function checking(arr, mid) {
  //거리에 따른 배치한 말의 수를 정의함
  let cnt = 1;
  let ef = arr[0];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - ef >= mid) {//텀이 더 클때는 넣어줘야함 
      cnt++;
      ef = arr[i];
    }//작을때는 흘려보낸다.
  }

  return cnt;
}

최대 거리를 탐색하는 문제이다. 어려웠던 점은
전 뮤직비디오에서는 가장 적은 dvd가 목표여서 최저치를 구했는데
최대치를 구하는 문제여서 어려움을 느꼈다.

결과에 따른 환경 변수를 잘 인지해야겠다.

그래서 이분 탐색을 할 때 lt, rt 뭐를 써줘야하는지 잘기억하자.