[프로그래머스] 코딩테스트 연습 (JavaScript) | 교공 알고리즘 스터디 45주차

코딩테스트 연습 | 문제 바로가기

✔ 아래의 캡쳐본은 문제의 일부입니다.
보다 자세한 제한 사항 및 입출력 예시는 위의 링크를 참고해주세요!

⭐ 풀이의 핵심

DP(Dynamic Programming)로 풀 수 있는 문제이다
예전에는 dp라면 진짜 일도 감이 안 왔는데.. 그래도 많이 컸다..

dp[i][j]: 알고력 i와 코딩력 j를 얻는 최단시간 으로 정의하고 문제를 풀면 된다

코딩력 또는 알고력을 높이는 방법에는 세 가지가 있다
각각의 방법에 따라 dp 배열을 업데이트 한다

🚨 단, 문제를 풀어서 알고력과 코딩력이 늘었을 때,
해당 값들이 목표(최대) 알고력 또는 목표(최대) 코딩력을 초과하는 경우
DP 배열에 접근할 때 런타임 에러가 날 수 있기 때문에
목표(최대) 알고력 또는 목표(최대) 코딩력으로 DP 배열의 인덱스를 처리해주어야만 한다

• 알고리즘 공부: 알고력 1을 높이기 위해 1의 시간 필요
  • dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1)
• 코딩 공부: 코딩력 1을 높이기 위해 1의 시간이 필요
  • dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1)
• 문제 풀기: 현재 풀 수 있는 문제 중 하나를 풀어 알고력과 코딩력을 높이며 문제마다 문제를 풀면 올라가는 알고력과 코딩력, 필요 시간이 정해져 있음
  • 문제를 풀면 목표 알고력과 목표 코딩력을 모두 초과하게 되는 경우
    • dp[alpMax][copMax] = Math.min(dp[alpMax][copMax], dp[i][j] + cost)
  • 목표 알고력만 초과하게 되는 경우
    - dp[alpMax][j+copRwd] = Math.min(dp[alpMax][j+copRwd], dp[i][j] + cost)
  • 목표 코딩력만 초과하게 되는 경우
    - dp[i+alpRwd][copMax] = Math.min(dp[i+alpRwd][copMax], dp[i][j] + cost)
  • 목표 알고력과 목표 코딩력을 모두 초과하지 않는 경우
    • dp[i+alpRwd][j+copRwd] = Math.min(dp[i+alpRwd][j+copRwd], dp[i][j]+cost)

참고로 2022 테크 여름인턴십 코딩테스트 해설을 살펴보면 다익스트라 알고리즘을 사용해서 풀 수도 있다고 언급되어 있다 조만간 다익스트라를 활용해서도 풀어봐야 겠다

⏱ 복잡도

O(목표(최대)알고력 * 목표(최대)코딩력 * problems 배열의 길이)

📝 유용한 JavaScript 메서드 정리

• Array.from()
  • 유사 배열 객체나 반복 가능한 객체를 얕게 복사해 새로운 Array 객체를 만드는 메서드
  • 2차원 배열 초기화할 시에 유용하게 활용 가능
  • Array.from(arrayLike[, mapFn[, thisArg]])
    • arrayLike : 배열로 변환하고자 하는 유사 배열 객체나 반복 가능한 객체
    • mapFn : 배열의 모든 요소에 대해 호출할 맵핑 함수
    • thisArg : mapFn 실행 시에 this로 사용할 값
  • [참고] Array.from() - JavaScript | MDN

console.log(Array.from("daeun"));
// ['d', 'a', 'e', 'u', 'n']

console.log(Array.from([1,2,3], x => x + 2));
// [3, 4, 5]

const visited = Array.from(new Array(3), () => new Array(3).fill(0));
// [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

✅ 최종 코드

const solution = (alp, cop, problems) => {
    const MAX_INT = 2147483647;
    
    // 목표 알고력 및 코딩력 구하기
    let alpMax = 0;
    let copMax = 0;
    for (let i=0; i<problems.length; i++) {
        if (problems[i][0] > alpMax) alpMax = problems[i][0];
        if (problems[i][1] > copMax) copMax = problems[i][1];
    }
    if (alp > alpMax) alp = alpMax;
    if (cop > copMax) cop = copMax;
    
    // dp 배열 초기화
    const dp = Array.from(new Array(151), () => new Array(151).fill(MAX_INT));
    dp[alp][cop] = 0;
    
    for (let i=alp; i<=alpMax; i++) {
        for (let j=cop; j<=copMax; j++) {
            if (i == alpMax && j == copMax) break;
            
            // 1. 알고리즘 공부하기 -> 1을 높이기 위해서 1의 시간이 필요
            if (i < alpMax) {
                dp[i+1][j] = Math.min(dp[i+1][j], dp[i][j]+1);
            }
            
            // 2. 코딩 공부하기 -> 1을 높이기 위해서 1의 시간이 필요
            if (j < copMax) {
                dp[i][j+1] = Math.min(dp[i][j+1], dp[i][j]+1);    
            }
            
            // 3. 문제 풀기 -> 각 문제마다 문제를 풀면 올라가는 알고력과 코딩력이 정해져 있음 (같은 문제 여러 번 가능)
            for (let k=0; k<problems.length; k++) {
                const [alpReq, copReq, alpRwd, copRwd, cost] = problems[k];
                
                // (현재 풀 수 있는 문제만 풀 수 있기 때문에 아래의 if 조건문 추가)
                if (i >= alpReq && j >= copReq) {
                    const alpSum = i + alpRwd;
                    const copSum = j + copRwd;
                    
                    if (alpSum >= alpMax && copSum >= copMax) {
                        dp[alpMax][copMax] = Math.min(dp[alpMax][copMax], dp[i][j] + cost);
                    }
                    else if (alpSum >= alpMax) {
                        dp[alpMax][j+copRwd] = Math.min(dp[alpMax][j+copRwd], dp[i][j] + cost);
                    }
                    else if (copSum >= copMax) {
                        dp[i+alpRwd][copMax] = Math.min(dp[i+alpRwd][copMax], dp[i][j] + cost);
                    }
                    else {
                        dp[i+alpRwd][j+copRwd] = Math.min(dp[i+alpRwd][j+copRwd], dp[i][j] + cost);
                    }
                }
            }
        }
    }
    
    return dp[alpMax][copMax];
}