아찌방 하우스

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

풀이 - 나의 생각

전형적인 다익스트라 알고리즘에다가

비교연산 한 번이 추가 된 문제입니다.

무지와 어파치가 각자의 목적지 'A' 와 'B'에

최소한의 비용으로 가는 방법을 알기 위해서는

결국에 모든 목적지에 최소한의 비용으로 가는 방법을 알아야합니다.

그렇기에

int[] distFromStart = dijkstra(graph, n, s);
int[] distFromA = dijkstra(graph, n, a);
int[] distFromB = dijkstra(graph, n, b);

우선 출발지에서 모든 지점으로의 최소 비용을 구합니다.

A와 B에서 모든 지점의 최소 비용을 구합니다.

그 후 세가지 경우의 합을 비교합니다.

그 이유는

우리가 고려해야하는 경우는

1. 일정 지점까지 동행 후, 그 지점부터 각자의 목적지를 가는 경우

2. 처음부터 각자 가는 경우

두가지 입니다.

출발지에서 시작하는 다익스트라는 일정 지점까지 동행하는 경우를,

A, B에서 출발하는 다익스타는 일정 지점에서부터 각자가 간 경우를 알 수 있게 합니다.

그렇기에 세개의 배열의 합은

목적지까지의 비용을 나타내게 되는겁니다.

코드

import java.util.*;

class Node implements Comparable<Node>{
    int index;
    int cost;
    
    public Node(int index, int cost){
        this.index = index;
        this.cost = cost;
    }
    
    @Override
    public int compareTo(Node other){
        return Integer.compare(this.cost, other.cost);
    }
}

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] graph = new int[n+1][n+1];
        //그래프 초기화 및 값 입력
        for(int i = 1; i <= n; i++){
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }
        for(int[] fare : fares){
            graph[fare[0]][fare[1]] = fare[2];
            graph[fare[1]][fare[0]] = fare[2];
        }
        
        int[] distFromStart = dijkstra(graph, n, s);
        int[] distFromA = dijkstra(graph, n, a);
        int[] distFromB = dijkstra(graph, n, b);
        
        int minCost = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++){
            if(distFromStart[i] != Integer.MAX_VALUE && distFromA[i] != Integer.MAX_VALUE && distFromB[i] != Integer.MAX_VALUE){
                minCost = Math.min(minCost, distFromStart[i] + distFromA[i] + distFromB[i]);
            }
        }
        
        return minCost;
    }
    
    private int[] dijkstra(int[][] graph, int n, int start){
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int current = node.index;
            int cost = node.cost;
            
            //가야할 곳의 비용이 기존의 비용보다 비싸면 pass
            if(cost > dist[current]) continue;
            
            for(int i = 1; i <= n; i++){
            	//자기 자신의 위치, 연결이 안된 곳은 pass
                if(graph[current][i] == Integer.MAX_VALUE) continue;
                
                int newDist = cost + graph[current][i];
                //새로운 최소 비용일 시 갱신
                if(newDist < dist[i]){
                    dist[i] = newDist;
                    pq.add(new Node(i, newDist));
                }
            }
        }
        
        return dist;
    }
}

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

풀이 - 나의 생각

PriorityQueue를 2개 쓰면 된다.

(한개는 최솟값, 한개는 최댓값을 위한)

PriorityQueue는 기본적으로는 오름차순으로 정렬된다.

내림차순을 원한다면

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

이런식으로 해줘야 한다.

코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> maxQueue = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        PriorityQueue<Integer> minQueue = new PriorityQueue<>();
        
        for(String op : operations){
            String[] tmp = op.split(" ");
            int num = Integer.parseInt(tmp[1]);
            if(tmp[0].equals("I")){
                maxQueue.offer(num);
                minQueue.offer(num);
            }else{
                if(num == 1 && !maxQueue.isEmpty()){
                    int max = maxQueue.poll();
                    minQueue.remove(max);
                }else if(!minQueue.isEmpty()){
                    int min = minQueue.poll();
                    maxQueue.remove(min);
                }
            }
        }
        
        int min = 0, max = 0;
        
        if(!maxQueue.isEmpty()){
            min = minQueue.poll();
            max = maxQueue.poll();
        }
        
        return new int[] {max,min};
    }
}