프로그래머스(디스크 컨트롤러, 섬 연결하기) - Java

[디스크 컨트롤러]

https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러

 

* 조건

1. 작업 요청 시간과 작업 소요 시간이 입력된다
2. 하드디스크는 한 번에 하나의 작업만 수행 가능하다
3. 작업의 요청부터 종료까지 걸린 시간(대기 시간): 실제 작업 종료 시간 - 작업 요청 시간
4. 대기시간들의 평균이 제일 적은 값을 출력한다

* 알고리즘

• 힙 구조를 활용한 우선순위 큐 또는 일반 정렬

 

* 로직(Logic)

• 작업 소요 시간이 적은 작업부터 진행하면 대기 시간이 줄어드는 규칙이 존재한다
• 작업 소요 시간 순으로 오름차순 정렬 + 만약 소요 시간이 같다면 요청 시간이 더 낮은 순으로 정렬한다
• 현재 소요된 시간 내에서 실행할 수 있는 작업을 찾고
  • 현재 소요 시간 += 실행한 작업의 소요 시간
  • 대기시간을 추가
  • 마킹을 해준다
• 만약 현재 소요 시간 내에 가능한 작업이 없다면 1초를 늘려준다
• 모든 작업을 끝냈다면 종료한다
• 평균을 출력한다
  

import java.util.ArrayList;
import java.util.Arrays;

class DiskInfo implements Comparable<DiskInfo>{
    public int reqTime;     //요청시간
    public int doTime;      //작업소요시간

    public DiskInfo(int reqTime, int doTime) {
        this.reqTime = reqTime;
        this.doTime = doTime;
    }

    @Override
    public int compareTo(DiskInfo o) {
        if(this.doTime > o.doTime) return 1;
        else if(this.doTime == o.doTime){
            if(this.reqTime > o.reqTime) return 1;
            return -1;
        }

        return -1;
    }
}

public class Problem_DiskController {

    public static void main(String[] args) {
        int[][] jobs = { {0, 3}, {1, 9}, {2, 6} };
        int answer = solution(jobs);

        System.out.println(answer);
    }

    public static int solution(int[][] jobs) {
        int answer = 0;
        int jobSize = jobs.length;
        DiskInfo[] diskInfos = new DiskInfo[jobSize];
        boolean[] checked = new boolean[jobSize];

        for(int i = 0; i< jobSize; ++i){
            diskInfos[i] = new DiskInfo(jobs[i][0], jobs[i][1]);
        }
        Arrays.sort(diskInfos);

        int currentTime = 0;
        int acc = 0;
        int diskSize = diskInfos.length;
        while (diskSize>0){
            boolean find = false;
            for(int i=0; i<jobSize; ++i){
                if(!checked[i] && currentTime >= diskInfos[i].reqTime){
                    checked[i] = true;
                    find = true;
                    diskSize--;

                    currentTime += diskInfos[i].doTime;
                    acc = acc + (currentTime - diskInfos[i].reqTime);
                    break;
                }
            }
            if(!find) currentTime += 1;
        }

        answer = acc / jobSize;
        return answer;
    }
}

 

---

[섬 연결하기]

https://programmers.co.kr/learn/courses/30/lessons/42861

코딩테스트 연습 - 섬 연결하기

 

* 조건

1. n개의 섬이 주어지고, 연결 가능한 노드 및 비용이 입력된다
2. 모든 섬을 최소 비용으로 연결해야한다
3. 최소 비용을 출력한다
   
   

* 알고리즘

• 최소비용신장트리 (크루스칼 or 프림)

 

* 로직(Logic)

• 가중치를 기준으로 오름차순 정렬을 한다
• 초기에는 각 노드의 부모를 자기 자신으로 설정한다
• find, union을 사용한다
• 정렬된 순서대로 간선을 놓다가 만약 두 노드의 부모가 같다면 사이클이 형성되기 때문에 건너뛴다 (find)
• 두 노드의 부모가 같지 않다면 cost를 추가해주고 두 노드를 하나의 집합으로 만든다 (union)
• cost를 출력한다

 

<크루스칼 알고리즘>

import java.util.Arrays;

class Edge implements Comparable<Edge>{
    public int v1, v2;
    public int cost;

    public Edge(int v1, int v2, int cost) {
        this.v1 = v1;
        this.v2 = v2;
        this.cost = cost;
    }

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

public class Problem_ConnectIsland {
    static int[] parent;

    public static void main(String[] args) {
        int n = 4;
        int[][] costs = {
                //v1, v2, cost
                {0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8}
        };

        int ans = solution(n, costs);
        System.out.println(ans);
    }

    public static int solution(int n, int[][] costs) {
        int answer = 0;
        int edgeSize = costs.length;
        Edge[] edges = new Edge[edgeSize];

        for(int i=0; i<edgeSize; ++i){
            edges[i] = new Edge(costs[i][0], costs[i][1], costs[i][2]);
        }
        Arrays.sort(edges);

        parent = new int[n];
        for(int i=0; i<n; ++i){
            parent[i] = i;
        }

        int cost = 0;
        for(int i=0; i<edgeSize; ++i){
            Edge edge = edges[i];
            if(!isSameParent(edge.v1, edge.v2)){
                cost += edge.cost;
                union(edge.v1, edge.v2);
            }
        }
        answer = cost;
        return answer;
    }

    private static void union(int v1, int v2) {
        v2 = findParent(v2);
        parent[v2] = v1;
    }

    private static boolean isSameParent(int v1, int v2) {
        v1 = findParent(v1);
        v2 = findParent(v2);

        if(v1 == v2) return true;
        return false;
    }

    private static int findParent(int v) {
        if(parent[v] == v){
            return v;
        }

        return parent[v] = findParent(parent[v]);
    }
}

 

<프림 알고리즘>

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Problem_ConnectIsland {

    static class EdgeInfor implements Comparable<EdgeInfor>{
        public int v1,v2;
        public int cost;

        public EdgeInfor(int v1, int v2, int cost) {
            this.v1 = v1;
            this.v2 = v2;
            this.cost = cost;
        }

        @Override
        public int compareTo(EdgeInfor o) {
            return this.cost - o.cost;
        }
    }

    static ArrayList<EdgeInfor>[] edges;
    static int N;

    public static void main(String[] args) {
        int n = 4;
        int[][] costs = {
                {0,1,1},{0,2,2},{1,2,5},{1,3,1},{2,3,8}
        };
        int answer = solution(n, costs);
        System.out.println(answer);
    }

    public static int solution(int n, int[][] costs) {
        int answer = 0;
        N = n;
        edges = new ArrayList[n];
        for(int i=0; i<n; ++i){
            edges[i] = new ArrayList<>();
        }

        for(int[] input : costs){
            int v1 = input[0];
            int v2 = input[1];
            int cost = input[2];

            edges[v1].add(new EdgeInfor(v1, v2, cost));
            edges[v2].add(new EdgeInfor(v2, v1, cost));
        }

        int startNode = 0;
        answer = doPrim(startNode);

        return answer;
    }

    private static int doPrim(int startNode) {
        boolean[] checked = new boolean[N];
        PriorityQueue<EdgeInfor> priorityQueue = new PriorityQueue<>();

        //시작노드와 인접한 간선 추가
        for(EdgeInfor node : edges[startNode]){
            priorityQueue.offer(node);
        }
        checked[startNode] = true;

        int cost = 0;
        while (!priorityQueue.isEmpty()){
            EdgeInfor q = priorityQueue.poll();
            if(checked[q.v2]) continue;

            checked[q.v2] = true;
            cost += q.cost;

            //인접한 노드의 간선 찾기
            for(EdgeInfor node : edges[q.v2]){
                priorityQueue.offer(node);
            }
        }

        return cost;
    }
}