[2022 카카오 인턴십 코테] 코딩 테스트 공부

링크

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

 

분류

완전탐색

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

알고리즘 공부를 하는것과 코딩 공부를 하는것 역시 problem 인 것 처럼 처리하면 코드 길이를 줄일 수 있음.

각각 [0, 0, 1, 0, 1], [0, 0, 0, 1, 1] 과 같음.

모든 problem을 풀기 위해 필요한 알고력 코딩력을 먼저 구한 다음

현재 내 상태에서 풀 수 있는 문제를 풀었을 때 바뀐 상태들을 큐에 넣어가면서 원하는 알고력과 코딩력을 가질 때 까지 반복함.

공부시간(cost)를 기준으로 정렬된 큐(priority queue)를 사용해야 시간 초과 나지 않음

 

시행착오

알고력 코딩력이 최대 150까지 요구될 수 있고 문제의 수는 최대 100개이므로..

최악의 경우 300^100의 반복이 필요하다

따라서 처음에 당황했지만 결과를 캐시하면서 처리해 경우의 수를 줄임

 

코드

import java.util.*;

class Solution {
    public int solution(int alp, int cop, int[][] problems) {
        int maxAlp = -1, maxCop = -1;
        int[][] ps = new int[problems.length + 2][5];
        boolean[][] visited = new boolean[2000][2000];


        for (int i = 0; i < problems.length; i++) {
            maxAlp = Math.max(maxAlp, problems[i][0]);
            maxCop = Math.max(maxCop, problems[i][1]);

            ps[i] = problems[i];
        }

        ps[ps.length - 2] = new int[]{0, 0, 1, 0, 1};
        ps[ps.length - 1] = new int[]{0, 0, 0, 1, 1};

        Queue<Q> queue = new PriorityQueue<>();
        queue.add(new Q(alp, cop, 0));

        while (!queue.isEmpty()) {
            Q q = queue.poll();
            
            if (visited[q.alp][q.cop]) continue;
            if (q.alp >= maxAlp && q.cop >= maxCop) return q.cost;

            for (int i = 0; i < ps.length; i++) {
                if (ps[i][0] > q.alp || ps[i][1] > q.cop) continue;

                queue.add(new Q(q.alp + ps[i][2], q.cop + ps[i][3], q.cost + ps[i][4]));
            }

            visited[q.alp][q.cop] = true;
        }

        return -1;
    }

    class Q implements Comparable<Q>{
        int cost, alp, cop;

        public Q(int alp, int cop, int cost) {
            this.alp = alp;
            this.cop = cop;
            this.cost = cost;
        }

        @Override
        public int compareTo(Q o) {
            if (o.cost < this.cost) return 1;
            if (o.cost > this.cost) return -1;
            return 0;
        }
    }
}