알고리즘 재활치료 14일차 - 10816, 15666, 1504번

아 더워 수영하고싶다

 

 

숫자 카드 2

 

 

 

카드의 개수가 몇개인지 파악해야하고, 없다면 0을 출력해야한다.

간단하게 HashMap 자료구조를 활용했고 getOrDefault 를 활용해서 개수 저장해줬다. 

5분커엇..

 

 

import java.io.*;
import java.util.*;
 
public class Main { // 숫자 카드 2
    public static int N, M;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        N = Integer.parseInt(st.nextToken());
        Map<Integer, Integer> set = new HashMap<>();
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            int temp = Integer.parseInt(st.nextToken());
            set.put (temp,set.getOrDefault(temp, 0) + 1 );
        }
 
        st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<M; i++){
            int temp = Integer.parseInt(st.nextToken());
            if(set.get(temp) == null){
                sb.append(0).append(" ");
            }else{
                sb.append(set.get(temp)).append(" ");
            }
        }
 
        System.out.println(sb);
    }
}
 

---

N과 M (12)

 

 

N과 M도 곧 다 풀어가네..

이번 12번은 중복되는 숫자를 사용해두 되지만 중복되는 수열만 사용안하면 된다.

또한 비내림차순으로 우측하단으로 갈수록 숫자가 커져야 한다.

start 변수로 반복함에 따라서 정렬된 arr에서 밀리지 않게 해주었다.

 

만약 숫자 N = 4, M = 2이고 숫자가 1,2,3,4 라면

1 1

1 2

1 3

1 4 이런식으로 진행하는 역할이다.

이렇게 작성하려면 중복되는 숫자들을 지워줘야 했기에 Set으로 제거하고 asArray쓰려다가

Stream을 연습중이라 사용해봤다.

Array를 먼저 Stream으로 변환해주고 distinct()를 활용해서 제거해줬다. 이후 다시 toArray로 바꿔주면 끝.

arr = Arrays.stream(arr).distinct().toArray();

 

import java.io.*;
import java.util.*;
 
public class Main { // N과 M (12)
    public static int N, M;
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        arr = Arrays.stream(arr).distinct().toArray();
        Arrays.sort(arr);
        N = arr.length; // 중복 제거 후 크기 조정
 
        dfs(0, 0, new int[M]);
 
        System.out.println(sb);
    }
 
    public static void dfs(int depth, int start, int[] answer) {
        if (depth == M) {
            for (int s : answer) {
                sb.append(s).append(" ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = start; i < N; i++) {
            answer[depth] = arr[i];
            dfs(depth + 1, i, answer); 
        }
    }
}
 

---

특정한 최단 경로

 

 

먼저 방향성이 없는 그래프가 주어지고, 1번부터 N번까지 도달하는데 이 중간에 두개의 정점을 꼮!!! 지나쳐야 한다.

한번 이동했던 간선도 다시 이동할 수 있다는 조건이 있어서 오히려 헷갈렸는데,

단순히 해당 위치에서 다익스트라 로직을 사용해주면 해결됐다.

 

다익스트라는 1에서 2로 이동하는데, 1->2 보다 cost가 적은 다른 경로들이 있다면 갱신하면서

출발점에서 모든 vertex까지의 비용을 갱신하는 알고리즘이다.

 

예제처럼 1부터 4까지 가는데, 2와 3을 꼭 지나쳐야 하는 경우를 계산해야 한다.

오늘도 발그림.. ㅎㅎ;ㅎ

경로는 1 - 2 - 3 - 4 아니면 1 - 3 - 2 - 4 이고

이중에 짧은걸 고르면 된다. 따라서 중간에 방문하는 경로를 route1, route2로 나눈다면

( start -> route1 ) + ( route1 > route2 ) + ( route2 > end ) 가 1번 Path일것이고

( start -> route2 ) + ( route2 > route1 ) + ( route1 > end ) 가 2번 Path이 된다.

이 둘중에서 더 짧은걸 출력해주면 되고, Integer.MAX_VALUE; 로 INF 를 표기했을때 덧셈하면 오버라이드되니

가볍게 처리해주자. INF라면 경로가 없는것이므로 -1를 출력해주었다.

 

 

import java.io.*;
import java.util.*;
 
public class Main { // 특정한 최단 경로
    public static int N, E;
    public static ArrayList<ArrayList<Node>> graph;
    public static int[] costs;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
 
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Node>());
        }
 
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            // 양방향
            graph.get(start).add(new Node(end, cost));
            graph.get(end).add(new Node(start, cost));
        }
 
        st = new StringTokenizer(br.readLine());
        int route1 = Integer.parseInt(st.nextToken());
        int route2 = Integer.parseInt(st.nextToken());
 
        int case1 = 0, case2 = 0;
 
        int path1 = dij(1, route1);
        int path2 = dij(route1, route2);
        int path3 = dij(route2, N);
        
        if (NonePathChk(path1, path2, path3)) {
            case1 = Integer.MAX_VALUE;
        } else {
            case1 = path1 + path2 + path3;
        }
 
        path1 = dij(1, route2);
        path2 = dij(route2, route1);
        path3 = dij(route1, N);
        
        if (NonePathChk(path1, path2, path3)) {
            case2 = Integer.MAX_VALUE;
        } else {
            case2 = path1 + path2 + path3;
        }
 
        int answer = Math.min(case1, case2);
        
        // 없는 경로 처리
        if (answer == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(answer);
        }
    }
 
    public static int dij(int start, int end) {
        costs = new int[N + 1];
        Arrays.fill(costs, Integer.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.cost));
        pq.add(new Node(start, 0));
        costs[start] = 0;
 
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int curV = cur.vertex;
            int curC = cur.cost;
 
            if (costs[curV] < curC) {
                continue;
            }
 
            for (Node next : graph.get(curV)) {
                int newC = curC + next.cost;
                if (newC < costs[next.vertex]) {
                    costs[next.vertex] = newC;
                    pq.add(new Node(next.vertex, newC));
                }
            }
        }
        return costs[end];
    }
    public static boolean NonePathChk(int a, int b, int c) {
        return (a == Integer.MAX_VALUE || b == Integer.MAX_VALUE || c == Integer.MAX_VALUE);
    }
 
    public static class Node {
        int vertex;
        int cost;
 
        Node(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }
    }
}