1. 호텔 대실(level 2)

- 문제

https://school.programmers.co.kr/learn/courses/30/lessons/155651

- 코드 작성 전 생각

1. 입력이 계산하기 어렵기 때문에 수정해야한다고 생각함.
   • 퇴실시간이 하루를 넘어가지 않는다는 조건이 있기 때문에 모든 시간을 분으로 바꿔서 하면 좋을 것 같다고 생각했다. (ex : 10시 30분 => 10 * 6 + 30 = 630분, 퇴실시간은 해당 로직에 청소시간까지 + 10을 해주는 식으로)
2. 방 개수를 어떻게 정할까를 생각하던 중 1번 과정을 통해 바뀐 배열을 예약 시작 시간을 기준으로 오름차순으로 정렬한 뒤, 끝나는 시간을 만들어 놓고 (다음 예약자의 시작시간 - 현재 이용자의 끝나는 시간 >= 0) 이면 방을 계속 쓰면서 끝나는 시간을 초기화 해주는 식으로 진행하면 될 것 같았다.

- 구현 중 추가 된 항목

1. 이미 방을 배정받은 사람이지 어떻게 표시를 해야할까에 대한 고민이 필요했다.

    if (newBookTime[i].length === 3) {
      continue;
    }
    room += 1;
    newBookTime[i].push(true);

   • 해당 방식과 같이 newBookTime[i] (i번째 예약자의 시간이 보관되어있음)에 true를 넣어줌으로서 해당 이용자는 방을 배정받았다고 표시를 했다.

- 코드

const toMinute = (array) => {
  return array
    .map((time) =>
      time.map((value, index) => {
        const times = value.split(":");
        if (index === 0) {
          return 60 * Number(times[0]) + Number(times[1]);
        }
        return 60 * Number(times[0]) + Number(times[1]) + 10;
      })
    )
    .sort((a, b) => a[0] - b[0]);
};

const solution = (book_time) => {
  const newBookTime = toMinute(book_time);
  let room = 0;
  for (let i = 0; i < newBookTime.length; i += 1) {
    if (newBookTime[i].length === 3) {
      continue;
    }
    room += 1;
    newBookTime[i].push(true);
    let end = newBookTime[i][1];
    let j = i + 1;
    while (j < newBookTime.length) {
      if (i === newBookTime.length - 1) {
        break;
      }
      if (newBookTime[j][0] - end >= 0 && newBookTime[j].length !== 3) {
        newBookTime[j].push(true);
        end = newBookTime[j][1];
      }
      j += 1;
    }
  }
  return room;
};

2. 마법의 엘리베이터(level 2)

- 문제

https://school.programmers.co.kr/learn/courses/30/lessons/148653#

- 코드 작성 전 생각

1. DFS를 통한 재귀로 풀면 될것 같다.
2. 최대 갯수가 100,000,000이기 때문에 단순구현으로도 가능할 것 같다.

- 구현 중 추가 된 항목

1. 단순하게 일의자리 숫자가 5보다 작을때, 클때, 5와 같을때를 기준으로 코드를 작성하면 된다.
2. 5보다 작을 경우 내림, 5보다 클 경우 올림, 5와 같을 경우 10의 자리수가 5미만이면 내림 5이상이면 올림으로 코드를 작성했다.

- 코드

const solution = (storey) => {
  let answer = 0;
  while (storey) {
    let cur = storey % 10;
    let next = Math.floor(storey / 10) % 10;
    if (cur > 5) {
      answer += 10 - cur;
      storey += 10;
    } else if (cur == 5) {
      answer += 5;
      storey += next >= 5 ? 10 : 0;
    } else answer += cur;
    storey = Math.floor(storey / 10);
  }
  return answer;
};

3. 숫자 타자 대회(level 3)

- 문제

https://school.programmers.co.kr/learn/courses/30/lessons/136797

- 코드 작성 전 생각

1. 브루탈 포스로 해볼까 했지만 시간복잡도가 2^100000이 되기 때문에 아예 불가능하다고 생각했다.
2. 한번 DP로 풀어보려고 생각을 해봤다.
3. DP로 풀기 위해선 3차원 배열이 필요했다(n번째 숫자, 왼손, 오른손)
4. 점화식을 생각하는데는 오래걸리지 않았다.

   DP[n][l][r] = Math.min(DP[n-1][k][r], DP[n-1][l][k])

- 구현 중 추가 된 항목

1. DP[0][4][6] = 0 이여야한다. 맨처음 4,6에 각 왼손 오른손이 올려져있기 때문이다.
2. 가중치에 관한 배열이 있어야한다.(코드로 짜면 좋았겠지만,,, 생각할 힘이 없어 그냥 노가다로 썼다.)
3. js의 flat 함수를 통해 2차원배열을 1차원으로 만들어서 가장 작은 값을 찾아 낼 수 있었다.(ex : a = [1,2,3,4,[5,6]] => a.flat() = [1,2,3,4,5,6]
4. 오류를 찾다가 같은 숫자를 누를 수 없다는 예외처리를 해야하는것을 까먹고 있었다.

   if (i === j || prevValue === Infinity) continue;

   • i === j 즉 왼손과 오른손이 겹칠 경우, dp[n-1][i][j]가 infinity라면 계산할 필요가 없기때문에 continue로 넘겨준다.

- 코드

const weights = [
  [1, 7, 6, 7, 5, 4, 5, 3, 2, 3],
  [7, 1, 2, 4, 2, 3, 5, 4, 5, 6],
  [6, 2, 1, 2, 3, 2, 3, 5, 4, 5],
  [7, 4, 2, 1, 5, 3, 2, 6, 5, 4],
  [5, 2, 3, 5, 1, 2, 4, 2, 3, 5],
  [4, 3, 2, 3, 2, 1, 2, 3, 2, 3],
  [5, 5, 3, 2, 4, 2, 1, 5, 3, 2],
  [3, 4, 5, 6, 2, 3, 5, 1, 2, 4],
  [2, 5, 4, 5, 3, 2, 3, 2, 1, 2],
  [3, 6, 5, 4, 5, 3, 2, 4, 2, 1],
];

const solution = (numbers) => {
  const DP = Array.from({ length: numbers.length + 1 }, () =>
    Array.from({ length: 10 }, () => new Array(10).fill(Infinity))
  );

  DP[0][4][6] = 0;

  for (let idx = 0; idx < numbers.length; idx += 1) {
    const num = numbers[idx];

    const prevDP = DP[idx];
    const nowDP = DP[idx + 1];

    for (let i = 0; i < 10; i += 1) {
      for (let j = 0; j < 10; j += 1) {
        const prevValue = prevDP[i][j];
        if (i === j || prevValue === Infinity) continue;
        
        if (nowDP[num][j] > prevValue + weights[i][num]) {
            nowDP[num][j] = prevValue + weights[i][num]
        }
          
        if (nowDP[i][num] > prevValue + weights[num][j]) {
            nowDP[i][num] = prevValue + weights[num][j]
        }
      }
    }
  }

  return Math.min(...DP[numbers.length].flat(2));
};