[2022 KAKAO TECH INTERNSHIP] 코딩 테스트 공부

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

프로그래머스

[문제 정의]

주어진 모든 문제를 풀 수 있는 알고력과 코딩력을 가진다는 말은, 주어진 problems 배열에서 가장 큰 값인 알고력과 코딩력을 가져야 한다는 말이다. 즉, (초기 알고력, 코딩력)에서 시작해서 (목표 알고력, 코딩력) 상태에 도달하는데 걸리는 최단 시간을 구하면 된다.

 

[구현]

그런데 현재의 알고력과 코딩력에서 알고력 및 코딩력을 늘릴 수 있는 방법은 다음과 같이 여러 방법이 있다.

• 알고리즘 공부
• 코딩 공부
• 문제를 풀기

그리고 여러 방법 중 "~한 상황에서는 ~한 방법이 최선"이라는 개념이 맞지 않다. 즉, 그리디 같은 알고리즘으로 푸는 문제가 아니다. 결론은 dp 문제이다. 이때 dp[i][j]는 코딩력 i, 알고력 j가 되기 위해 걸린 최단 시간이다. 따라서 알고력과 코딩력을 순차적으로 돌며, 현재의 알고력과 코딩력에서 알고력 및 코딩력을 늘릴 수 있는 방법을 모두 수행하고, dp 배열을 갱신해주면 된다.

 

[주의]

• 초기 알고력 및 코딩력이 목표 알고력 및 코딩력보다 클 수 있다(초기 값 > 목표 값). 따라서 이때는 더 큰 값을 목표로 설정해줘야 한다.
• 목표 알고력과 코딩력 이상의 알고력 및 코딩력을 갖는 것이 문제이다. 즉, 정확히 목표 알고력과 코딩력을 가질 필요 없이 그 이상의 값이면 된다. 따라서 다음 상황을 주의해야 한다.
  • 목표 알고력과 코딩력이 4이고, 현재의 알고력과 코딩력이 2라고 가정하자.
  • dp[2][2]에서 문제를 풀어서 dp[4][4] = 3이 되었다고 하고, 
  • dp[2][2]에서 또 다른 문제를 풀어서 dp[5][5] = 2가 되었다고 하자.
  • 즉, 목표 알고력과 코딩력이 되기 위한 최단 시간인 dp[4][4]를 답으로 제출하면 위와 같은 상황의 반례가 존재한다.
  • 따라서 목표 알고력과 코딩력을 넘어서는 값은 목표 알고력과 코딩력이라고 취급해야 한다. (목표 알고력 및 코딩력 == 목표 이상의 알고력 및 코딩력)(문제에서 취급하는 의미가 같다!)

import java.util.*;

class Solution {
    
    public int solution(int alp, int cop, int[][] problems) {

        int goalAlp = 0;
        int goalCop = 0;
        
        for (int[] problem : problems) {
            goalAlp = Math.max(goalAlp, problem[0]);
            goalCop = Math.max(goalCop, problem[1]);
        }
        
        goalAlp = Math.max(goalAlp, alp);
        goalCop = Math.max(goalCop, cop);
        
        int[][] dp = new int[goalAlp + 1][goalCop + 1];
        
        for (int[] arr : dp) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }
        dp[alp][cop] = 0;
        
        for (int i = alp; i <= goalAlp; i++) {
            for (int j = cop; j <= goalCop; j++) {
                
                // 알고리즘 공부
                if (i + 1 > goalAlp) {
                    dp[goalAlp][j] = Math.min(dp[goalAlp][j], dp[i][j] + 1);
                } else {
                    dp[i + 1][j] = Math.min(dp[i + 1][j], dp[i][j] + 1);
                }
                
                // 코딩 공부
                if (j + 1 > goalCop) {
                    dp[i][goalCop] = Math.min(dp[i][goalCop], dp[i][j] + 1);
                } else {
                    dp[i][j + 1] = Math.min(dp[i][j + 1], dp[i][j] + 1);
                }
                
                // 문제 풀기
                for (int[] problem : problems) {
                    if (i >= problem[0] && j >= problem[1]) {
                        int newAlp = i + problem[2];
                        int newCop = j + problem[3];
                        if (newAlp > goalAlp) newAlp = goalAlp;
                        if (newCop > goalCop) newCop = goalCop;
                        dp[newAlp][newCop] = Math.min(dp[newAlp][newCop], dp[i][j] + problem[4]);
                    }
                }
            }
        }
        
        return dp[goalAlp][goalCop];
    }
}

 

[다익스트라 풀이]

다음과 같이 다익스트라를 사용해서도 풀 수 있다!

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int goalAlp = 0;
        int goalCop = 0;
        for (int[] problem : problems) {
            goalAlp = Math.max(goalAlp, problem[0]);
            goalCop = Math.max(goalCop, problem[1]);
        }
        goalAlp = Math.max(goalAlp, alp);
        goalCop = Math.max(goalCop, cop);
        
        // 해당 알고력과 코딩력을 갖는데 걸리는 최단 시간
        int[][] time = new int[goalAlp + 1][goalCop + 1];
        for (int[] arr : time) {
            Arrays.fill(arr, Integer.MAX_VALUE);
        }
        
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(alp, cop));
        time[alp][cop] = 0;
        
        while (!que.isEmpty()) {
            Node now = que.poll();
            
            // 알고리즘 공부
            int newAlp = (now.alp + 1 > goalAlp) ? goalAlp : now.alp + 1;
            if (time[newAlp][now.cop] > time[now.alp][now.cop] + 1) {
                time[newAlp][now.cop] = time[now.alp][now.cop] + 1;
                que.add(new Node(newAlp, now.cop));
            }
            
            // 코딩 공부
            int newCop = (now.cop + 1 > goalCop) ? goalCop : now.cop + 1;
            if (time[now.alp][newCop] > time[now.alp][now.cop] + 1) {
                time[now.alp][newCop] = time[now.alp][now.cop] + 1;
                que.add(new Node(now.alp, newCop));
            }
            
            // 문제 풀기
            for (int[] problem : problems) {
                if ((now.alp >= problem[0]) && (now.cop >= problem[1])) {
                    newAlp = (now.alp + problem[2] > goalAlp) ? goalAlp : now.alp + problem[2];
                    newCop = (now.cop + problem[3] > goalCop) ? goalCop : now.cop + problem[3];
                    if (time[newAlp][newCop] > time[now.alp][now.cop] + problem[4]) {
                        time[newAlp][newCop] = time[now.alp][now.cop] + problem[4];
                        que.add(new Node(newAlp, newCop));
                    }
                }
            }
        }
        
        return time[goalAlp][goalCop];
    }
    
    private static class Node {
        
        int alp;
        int cop;
        
        public Node(int alp, int cop) {
            this.alp = alp;
            this.cop = cop;
        }
    }
}