[프로그래머스] Lv3 문제풀이7(feat. JAVA)

디스크 컨트롤

import java.util.*;
import java.util.stream.IntStream;

class Solution {
    class Job {
        int start;
        int cost;

        Job(int start, int cost) {
            this.start = start;
            this.cost = cost;
        }
    }

    public int solution(int[][] jobs) {
        int answer = 0;

        PriorityQueue<Job> heap = new PriorityQueue<>((o1, o2) -> {
            if(o1.start != o2.start)
                return o1.start - o2.start;
            else
                return o1.cost - o2.cost;
        });
        IntStream.range(0, jobs.length)
                .forEach(i -> heap.add(new Job(jobs[i][0], jobs[i][1])));
        PriorityQueue<Job> wlist = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);

        int end = 0;

        while(true) {
            Job j = null;
            if(!wlist.isEmpty()) {
                j = wlist.poll();
            } else {
                if(heap.isEmpty()) break;
                j = heap.poll();
                end = j.start;
            }

            end += j.cost;
            answer += end - j.start;

            while(!heap.isEmpty() && heap.peek().start <= end){
                wlist.add(heap.poll());
            }
        }

        return answer/ jobs.length;
    }
}

 

 

 

경주로 건설

import java.util.*;

class Solution {
    public class Point {
        int x;
        int y;
        int d;
        int cost;
        Point(int x, int y, int d, int cost) {
            this.x = x;
            this.y = y;
            this.d = d; // 0 : horizontal  1 : vertical
            this.cost = cost;
        }
    }
    public int solution(int[][] board) {
        int answer = Integer.MAX_VALUE;
        int[][][] dp = new int[2][board.length][board.length];

        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < board.length; j++) {
                Arrays.fill(dp[i][j], Integer.MAX_VALUE);
            }
        }

        Deque<Point> q = new LinkedList<>();
        q.add(new Point(0, 1, 0, 100));
        q.add(new Point(1, 0, 1, 100));

        while(!q.isEmpty()) {
            Point temp = q.pollFirst();
            int x = temp.x;
            int y = temp.y;
            int d = temp.d;
            int cost = temp.cost;

            if (x == board.length - 1 && y == board.length - 1) {
                if (answer > cost) {
                    answer = cost;
                    continue;
                }
            } else if (x < 0 || x >= board.length || y < 0 || y >= board.length) {
                continue;
            } else if (dp[d][x][y] < cost) {
                continue;
            } else if (board[x][y] == 1) {
                continue;
            }

            dp[d][x][y] = cost;

            if(d == 0) {
                q.add(new Point(x , y + 1, 0, cost + 100));
                q.add(new Point(x , y - 1, 0, cost + 100));
                q.add(new Point(x + 1, y, 1, cost + 600));
                q.add(new Point(x - 1, y, 1, cost + 600));
            } else {
                q.add(new Point(x , y + 1, 0, cost + 600));
                q.add(new Point(x , y - 1, 0, cost + 600));
                q.add(new Point(x + 1, y, 1, cost + 100));
                q.add(new Point(x - 1, y, 1, cost + 100));
            }
        }

        return answer;
    }
}

 

 

 

입국심사

class Solution {
    public long solution(int n, int[] times) {
        long min = 1;
        long max = (long)times[0] * n;

        while(min < max) {
            long mid = (min + max) / 2;

            int cnt = 0;
            for(int i : times) {
                cnt += mid / i;
                if(cnt > n) break;
            }

            if(cnt < n) {
                min = mid + 1;
            } else {
                max = mid;
            }

        }

        return min;
    }
}