[프로그래머스] 코딩-테스트-공부.js

2022 KAKAO TECH INTERNSHIP - 코딩 테스트 공부

최단시간을 구하는 문제라서 DP방식으로 구현했다.

1. 목표 alp, cop의 기본값은 0이 아닌 현재 alp, cop

목표값은 기본값이 0, 0이 아닌 alp, cop가 되어야 한다

const [goalAlp, goalCop] = problems.reduce(([maxAlp, maxCop], [curAlp, curCop]) => {
    if (curAlp > maxAlp) maxAlp = curAlp;
    if (curCop > maxCop) maxCop = curCop;
    return [maxAlp, maxCop];
  }, [alp, cop]); // X: [0, 0]

2. Array().fill(Array.fill()) 방식으로 하면 배열이 복사된다

이런 방식으로 코드를 짜면 10개 배열이 같은 주소값을 가져서 버그가 날 가능성이 아주아주아주아주아주 높다...

Array(10).fill(Array(10).fill(Infinity));

다음과 같이 구현하자

Array.From({ length: 10}, () => Array(10).fill(Infinity));

3. 문제의 rwdAlp, rwdCop 인덱스가 초과될 경우

문제를 풀 수 있을 때 rwdAlp, rwdCop 이 초과될 수도 있다. 이럴때는 최대 alp, cop 값으로 해서 dp값을 최신화해야한다.

정답코드

function solution(alp, cop, problems) {
  const [goalAlp, goalCop] = problems.reduce(([maxAlp, maxCop], [curAlp, curCop]) => {
    if (curAlp > maxAlp) maxAlp = curAlp;
    if (curCop > maxCop) maxCop = curCop;
    return [maxAlp, maxCop];
  }, [alp, cop]);

  const dp = Array.from({ length: goalAlp + 1 }, () => Array(goalCop + 1).fill(Infinity));
  dp[alp][cop] = 0;

  for (let curAlp = alp; curAlp <= goalAlp; curAlp += 1) {
    for (let curCop = cop; curCop <= goalCop; curCop += 1) {
      if (curAlp + 1 <= goalAlp) {
        dp[curAlp + 1][curCop] = Math.min(dp[curAlp + 1][curCop], dp[curAlp][curCop] + 1);
      }
      if (curCop + 1 <= goalCop) {
        dp[curAlp][curCop + 1] = Math.min(dp[curAlp][curCop + 1], dp[curAlp][curCop] + 1);
      }

      problems.forEach(([reqAlp, reqCop, rwdAlp, rwdCop, cost]) => {
        if (curAlp < reqAlp || curCop < reqCop) return;
        const nextAlp = curAlp + rwdAlp > goalAlp ? goalAlp : curAlp + rwdAlp;
        const nextCop = curCop + rwdCop > goalCop ? goalCop : curCop + rwdCop;
        dp[nextAlp][nextCop] = Math.min(dp[nextAlp][nextCop], dp[curAlp][curCop] + cost);
      });
    }
  }

  return dp[goalAlp][goalCop];
}

console.log(
  solution(10, 10, [[10,15,2,1,2],[20,20,3,3,4]])
);