프로그래머스 코딩 테스트 공부 (JAVA)

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

프로그래머스

 

저는 우선순위 큐를 이용해 문제를 해결하였습니다.

먼저 problems에서 가장 큰 알고력과 코딩력을 찾습니다.

우선순위 큐를 통해 cost가 가장 낮은 것이 먼저 오도록 하였습니다.

3가지 경우로 진행하였습니다. 알고력과 cost를 1씩 올리거나, 코딩력과 cost를 1씩 올리거나, problems를 돌면서 알고력과 코딩력 둘 다 problem보다 높다면 이를 푸는 경우로 진행하였습니다.

방문 체크는 Set<String>으로 하여 해결하였습니다.

 

import java.util.*;
class Solution {
    private static final int alp_req_index = 0;
    private static final int cop_req_index = 1;
    private static final int alp_rwd_index = 2;
    private static final int cop_rwd_index = 3;
    private static final int cost_index = 4;
    
    public int solution(int alp, int cop, int[][] problems) {
        int answer = 0;
        int maxAlp = 0;
        int maxCop = 0;
        for(int[] problem : problems){
            maxAlp = Math.max(maxAlp,problem[alp_req_index]);
            maxCop = Math.max(maxCop,problem[cop_req_index]);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[2]-o2[2]);
        pq.offer(new int[] {alp,cop,0});
        Set<String> visited = new HashSet<>();
        while(!pq.isEmpty()){
            int[] now = pq.poll();
            if(now[0] >= maxAlp && now[1] >= maxCop){
                answer = now[2];
                break;
            }
            int[] next = new int[] {now[0]+1, now[1], now[2]+1};
            if(!visited.contains(Arrays.toString(next))){
                visited.add(Arrays.toString(next));
                pq.offer(next);
            }
            next = new int[] {now[0], now[1]+1, now[2]+1};
            if(!visited.contains(Arrays.toString(next))){
                visited.add(Arrays.toString(next));
                pq.offer(next);
            }
            for(int[] problem : problems){
                if(now[0] >= problem[alp_req_index] && now[1] >= problem[cop_req_index]){
                    next = new int[] {now[0] + problem[alp_rwd_index],now[1] + problem[cop_rwd_index],
                                     now[2]+problem[cost_index]};
                    if(!visited.contains(Arrays.toString(next))){
                        visited.add(Arrays.toString(next));
                        pq.offer(next);
                    }
                }
            }
        }
        return answer;
    }
}