[프로그래머스 - 자바] 코딩 테스트 공부

문제 링크

• 코딩 테스트 공부

풀이

• 카카오 인턴십 코테를 볼때는 해당 문제 효율성 테스트를 통과하지 못했다. 당시에는 엄청 어려운 문제인줄 알았는데, 이번에 다시 풀어보니 쉽게 풀 수 있었다!
• 주어진 조건들의 범위가 작아서 일차적으로 완전 탐색을 떠올렸다. 하지만 problems가 최대 100개까지 가능하기 때문에 시간 초과가 발생할 수 있다.
• 그래서 알고력과 코딩력에 대한 이차원 배열을 만든 후 다익스트라와 유사하게 풀이를 전개하였다. 이차원 배열의 초기값은 공부로 각각 1씩 올린 값으로 주었다.
• 만약 알고력만 최댓값을 넘어가는 경우에는 편의상 최댓값으로 세팅해주었다. 코딩력도 마찬가지이다.
  • 여기서 말하는 최댓값은 problems에서 필요 알고력이나 필요 코딩력의 최댓값을 말한다.
• 알고력이나 코딩력의 초기값이 각 최대값을 초과할수도 있다는 점을 주의하자.

코드

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int answer = 0;
        int maxAlp = 0, maxCop = 0;
        for (int[] p : problems) {
            maxAlp = Math.max(p[0], maxAlp);
            maxCop = Math.max(p[1], maxCop);
        }
        
        alp = Math.min(alp, maxAlp);
        cop = Math.min(cop, maxCop);
        
        int[][] dp = new int[maxAlp + 1][maxCop + 1];
        for (int al = alp; al <= maxAlp; al++) {
            for (int co = cop; co <= maxCop; co++) {
                if (co == cop) {
                    dp[al][co] = al;
                } else if (al == alp) {
                    dp[al][co] = co;
                } else {
                    dp[al][co] = Math.min(dp[al - 1][co], dp[al][co - 1]) + 1;
                }
            }
        }
        // System.out.println(dp[maxAlp][maxCop]);
        
        Queue<Point> que = new LinkedList<>();
        que.offer(new Point(alp, cop, 0));
        
        while (!que.isEmpty()) {
            Point point = que.poll();
            
            if (dp[point.al][point.co] < point.cost) {
                continue;
            }
            
            // System.out.println(point.al + " " + point.co);
            
            // alpReq, copReq, alpRwd, copRwd, cost
            int alpReq, copReq, alpRwd, copRwd, cost;
            int nextAlp, nextCop;
            for (int[] p : problems) {
                alpReq = p[0];
                copReq = p[1];
                alpRwd = p[2];
                copRwd = p[3];
                cost = p[4];
                nextAlp = Math.min(maxAlp, point.al + alpRwd);
                nextCop = Math.min(maxCop, point.co + copRwd);
                
                if (!(alpReq <= point.al && copReq <= point.co) ||
                   dp[nextAlp][nextCop] <= point.cost + cost) {
                    continue;
                }
                
                dp[nextAlp][nextCop] = point.cost + cost;
                que.offer(new Point(nextAlp, nextCop, point.cost + cost));
            }
            
            nextAlp = Math.min(maxAlp, point.al + 1);
            nextCop = Math.min(maxCop, point.co + 1);
            if (dp[nextAlp][point.co] > point.cost + 1) {
                dp[nextAlp][point.co] = point.cost + 1;
                que.offer(new Point(nextAlp, point.co, point.cost + 1));
            }
            
            if (dp[point.al][nextCop] > point.cost + 1) {
                dp[point.al][nextCop] = point.cost + 1;
                que.offer(new Point(point.al, nextCop, point.cost + 1));
            }
        }
        
        return dp[maxAlp][maxCop];
    }
}

class Point {
    int al;
    int co;
    int cost;
    
    public Point(int al, int co, int cost) {
        this.al = al;
        this.co = co;
        this.cost = cost;
    }
}