알고리즘 - 연습 문제 1

문제1)

• 최소 시간  0, 최대시간 60으로 잡고 이진탐색으로 품
• 중앙값 30분안에 의사 두명이 몇명까지진료가 가능한가? => 7m : 4명 / 10m: 3명 = total: 7 > n ...

import java.util.Arrays;

public class Practice1 {
    public static int solution(int n, int[] times) {
        if (times == null || times.length == 0) {
            return -1;
        }

        Arrays.sort(times);
        int left = 0;
        int right = times[times.length - 1] * n;

        while (left <= right) {
            int mid = (left + right) / 2;

            int cnt = 0;
            for (int i = 0; i < times.length; i++) {
                cnt += mid / times[i];
            }

            if (cnt < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        // Test code
        int n = 6;
        int[] times = {7, 10};
        System.out.println(solution(n, times));
    }
}

28

---

문제2)

• 투 포인터를 사용하여 p1, p2를 n개의 범위만큼 지정하여 투 포인터 사이에 종류가 몇 개인지 확인하며 한 칸씩 오른쪽으로 넘어가며 확인

public class Practice2 {
    public static int solution(int n, int[] plates, int types, int coupon) {
        if (plates == null || plates.length == 0) {
            return -1;
        }

        // 몇 번 접시를 얼마나 골랐는지 카운팅할 배열
        int[] selected = new int[types + 1];

        int cnt = 0;
        int max = 0;

        // 우선 처음부터 연속해서 골랐을 때 상태 업데이트
        for (int i = 0; i < n; i++) {
            if (selected[plates[i]] == 0) {
                cnt++;
            }
            selected[plates[i]]++;
        }
        max = cnt;

        for (int i = 1; i < plates.length; i++) {
            // 기존의 가장 많이 선택한 수보다 많이 선택되었으면,
            // 쿠폰 여부에 따라 추가
            if (max <= cnt) {
                if (selected[coupon] == 0) {
                    max = cnt + 1;
                } else {
                    max = cnt;
                }
            }

            int p1 = i - 1;
            int p2 = (i + n - 1) % plates.length; // 원형 배열처럼 선택 범위 지정을 위해

            // 앞 쪽에서 하나씩 선택 빼고
            selected[plates[p1]]--;
            if (selected[plates[p1]] == 0) {
                cnt--;
            }

            // 뒤 쪽에서 하나씩 선택 추가
            if (selected[plates[p2]] == 0) {
                cnt++;
            }
            selected[plates[p2]]++;
        }

        return max;
    }

    public static void main(String[] args) {
        // Test code
        int n = 4;
        int[] plates = {7, 9, 7, 30, 2, 7, 9, 25};
        int types = 30;
        int coupon = 30;
        System.out.println(solution(n, plates, types, coupon));
    }
}

5

---

문제3)

import java.util.ArrayList;

public class Practice3 {

    public static int solution(int n, int[] items) {
        if (items == null || items.length == 0) {
            return -1;
        }

        boolean[] used = new boolean[items.length + 1];

        // 초기 사용 상태 업데이트
        int idx = 0;
        int cnt = 0;
        while (cnt < n) {
            if (!used[items[idx]]) {
                used[items[idx]] = true;
                cnt++;
            }
            idx++;
        }

        int result = 0;
        while (idx < items.length) {
            // 이번에 사용하려는 전기용품이 연결되어 있지 않은 경우
            if (!used[items[idx]]) {
                // 현재 콘센트에 연결된 용품 중 나중에 다시 사용하게 될 용품은 list 에 추가
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = idx; i < items.length; i++) {
                    if (used[items[i]] && !list.contains(items[i])) {
                        list.add(items[i]);
                    }
                }

                // 콘센트에 연결된 용품 모두 나중에 다시 사용하는 경우 순서상 나중에 사용할 용품 먼저 빼기
                if (list.size() == n) {
                    used[list.get(n - 1)] = false;
                } else {
                    // 그 외에는 앞으로 사용하지 않는 용품 1개 빼기
                    for (int j = 1; j <= items.length; j++) {
                        if (used[j] && !list.contains(j)) {
                            used[j] = false;
                            break;
                        }
                    }
                }

                // 새롭게 연결할 item 업데이트
                used[items[idx]] = true;
                result++;
            }
            idx++;
        }

        return result;
    }

    public static void main(String[] args) {
        // Test code
        int n = 2;
        int[] items = {2, 3, 2, 3, 1, 2, 7};
        System.out.println(solution(n, items));
    }
}

2

---

문제4)

• 나무 별로 포도가 떨어지는 표 준비 / 0번 움직였을 때 각 나무 별 최대 포도 획득 갯수
• 1번 움직였을 때 최대 포도 획득 갯수 / 2번 움직였을 때 최대 포도 획득 갯수 
• 총 4개의 표가 나옴 => 3차원 배열 dp를 만들기 위해 그려보면서 문제 풀어야 함

public class Practice4 {
    final static int numOfTree = 2;

    public static int solution(int[] order, int k) {
        if (order == null || order.length == 0) {
            return -1;
        }

        int n = order.length;
        int[][][] dp = new int[k + 2][numOfTree + 1][n];

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < k + 2; j++) {
                if (order[i] == 1) {    // 1번 나무 쪽에서 떨어질 때
                    dp[j][1][i] = Math.max(dp[j][1][i - 1], dp[j - 1][2][i - 1]) + 1; // 1번 나무
                    dp[j][2][i] = Math.max(dp[j][2][i - 1], dp[j - 1][1][i - 1]); // 2번 나무
                } else {    // 2번 나무 쪽에서 떨어질 때
                    if (i == 1 && j == 1) {
                        // 이동하지 않는 case 일 때 1 번 나무에서 시작하므로 continue
                        continue;
                    }

                    dp[j][1][i] = Math.max(dp[j][1][i - 1], dp[j - 1][2][i - 1]);
                    dp[j][2][i] = Math.max(dp[j][2][i - 1], dp[j - 1][1][i - 1]) + 1;
                }
            }
        }

        int result = 0;
        for (int i = 1; i < k + 2; i++) {
            result = Math.max(result, Math.max(dp[i][1][n - 1], dp[i][2][n - 1]));
        }

        return result;
    }

    public static void main(String[] args) {
        // Test code
        int[] order = {2, 1, 1, 2, 2, 1, 1};
        int k = 2;
        System.out.println(solution(order, k));
    }
}

6

---

문제5)

• 4개의 건물 / 5개의 경로 => 최악 경로와 최적 경로의 차이를 구해야 함
• 계산이 들어가는 부분은 오르막길 부분 뿐인 셈 => 오르막길 카운팅에 주의해서 각각 이를 제곱한 값의 차 구하기
• 최적 경로 => 내리막 길부터 간선 정보를 선택하도록 sorting
• 최악 경로 => 오르막 길부터 간선 정보를 선택하도록 sorting

import java.util.ArrayList;
import java.util.Collections;

public class Practice5 {

    static class Edge {
        int from;
        int to;
        int weight;

        Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    static int[] parents;
    static ArrayList<Edge> edgeList; // 경로 관리 변수

    public static int solution(int n, int m, int[][] data) {
        if (data == null || data.length == 0 || data[0].length == 0) {
            return -1;
        }

        // 엣지 구성
        edgeList = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            edgeList.add(new Edge(data[i][0], data[i][1], data[i][2]));
        }

        // 최악의 경로: 오르막길 부터 선택 되도록 (0: 오르막길)
        Collections.sort(edgeList, (x, y) -> x.weight - y.weight); // 오름차순 정렬
        int weightSum1 = kruskal(n, edgeList);

        // 최적의 경로: 내리막길 부터 선택 되도록(1: 내리막길)
        Collections.sort(edgeList, (x, y) -> y.weight - x.weight);
        int weightSum2 = kruskal(n, edgeList);

        return weightSum1 * weightSum1 - weightSum2 * weightSum2;
    }

    public static int kruskal(int n, ArrayList<Edge> edges) {
        parents = new int[n + 1];
        for (int i = 0; i < n + 1; i++) {
            parents[i] = i;
        }

        int weightSum = 0;
        for (int i = 0; i < edges.size(); i++) {
            Edge edge = edges.get(i);

            if (find(edge.from) != find(edge.to)) {
                union(edge.from, edge.to);

                if (edge.weight == 0) {
                    weightSum++;
                }
            }
        }

        return weightSum;
    }

    public static void union(int a, int b) {
        int aP = find(a);
        int bP = find(b);

        if (aP != bP) {
            parents[aP] = bP;
        }
    }

    public static int find(int a) {
        if (a == parents[a]) {
            return a;
        }
        return parents[a] = find(parents[a]);
    }

    public static void main(String[] args) {
        // Test code
        int n = 4;
        int m = 5;
        int[][] data = {{1, 2, 0}, {1, 4, 0}, {2, 3, 0}, {3, 4, 1}, {4, 2, 1}};

        System.out.println(solution(n, m, data));
    }
}

8