우선순위 큐9 [백준] 23843: 콘센트 - JAVA https://www.acmicpc.net/problem/23843 풀이충전기 m개로 n개의 전자기기를 충전해야한다. 전자기기마다 충전이 완료되는데 필요한 시간이 달라서 충전기에 전자기기를 적절하게 배치해야한다. 충전기가 비어있다면 충전에 걸리는 시간이 가장 긴 기기를 배치하는 게 적절했다. 따라서 우선순위큐를 이용해 시간이 오래걸리는 순으로 뽑아서 충전기에 넣었다. 충전기에 넣으면서 걸리는 시간을 정답에 갱신하면된다. 메모리: 15476KB시간: 180ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Charger { PriorityQueue chargers; Priority.. 2024. 5. 22. [백준] 19598: 최소 회의실 개수 - JAVA https://www.acmicpc.net/problem/19598 풀이회의의 시작, 종료 시간이 주어지고 최의실을 배정해야 한다. 회의실의 개수를 최소로 해야한다. 시작시간 순으로 정렬을해서 차례대로 회의실에 집어넣었다. 우선순위큐에 종료시간을 넣고, 우선순위큐의 peek이 새로 들어갈 회의의 시작시간보다 작다면 그 방을 사용할 수 있다. 메모리: 48764KB시간: 668ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2024. 5. 17. [백준] 2075: 스카이라인 쉬운거 - JAVA https://www.acmicpc.net/problem/2075 풀이왼쪽부터 순서대로 좌표가 주어지므로 높이만 stack에 저장하면 된다. 스택에 높이를 저장하면서 stack.peek()보다 높이가 낮아지면 stack.peek()이 더 낮아질때까지 pop해주면서 답을 하나씩 늘린다. 그리고 새로운 높이를 스택에 저장한다. 주의할 점으로 높이가 0이면 저장을 안해도 되고, stack.peek()과 높이가 같으면 저장을 안해도 된다는 것이있다. 메모리: 19576KB시간: 212ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception {.. 2024. 5. 17. [백준] 2075: N번째 큰 수 - JAVA https://www.acmicpc.net/problem/2075 풀이N \* N 개의 숫자 중에 N번째로 큰 숫자를 찾아야 한다. 우선순위큐를 사용해 정렬방식을 내림차순으로 하여 N개만큼 뽑는 방법이 있다. 이때는 `Collections.reverseOrder()` 를 사용해야 한다. 나는 오름차순 우선순위큐의 사이즈를 N으로 유지시키면서 값을 집어넣고 마지막에 하나를 뽑기로 했다. 이렇게하면 가장 큰 수 N개가 우선순위큐에 들어있게 되고, poll하면 N번째로 큰 숫자가 나온다. 메모리: 244104KB시간: 944ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[].. 2024. 5. 17. [백준] 13334: 철로 - JAVA https://www.acmicpc.net/problem/13334 풀이n명의 사람에 대해 2개씩 점의 위치가 주어지고, d길이의 선을 위치했을 때 2개의 점이 모두 선 안에 있는 사람의 최댓값을 구하는 문제이다. 입력을 받으면서 우선순위큐에 저장했다. 우선순위큐의 정렬 조건은 오른쪽 점을 오름차순으로, 오른쪽 점이 같을 경우 왼쪽 점을 오름차순으로 했다. 또 다른 우선순위큐을 만들어 개수를 세는 용도로 사용했다. 첫번째 우선순위큐를 pq라 하고, 두번째 우선순위큐를 count라고 했다. pq에서 값을 빼서 count에 넣는다. 이때 선분 d의 오른쪽 점을 pq에서 뺀 값의 오른쪽 점으로 하고, 이 선분에 왼쪽 점이 속해있지 않는 값들을 count에서 뺀다. 그 후 최댓값을 count의 size와 비교하.. 2024. 5. 16. [백준] 28703: Double It - JAVA https://www.acmicpc.net/problem/28703 풀이배열에서 수 하나를 골라 2를 곱하는 동작을 반복한다. 이렇게 동작하는 중에 배열의 최댓값과 최솟값의 차이를 구하는 문제이다. 처음 배열의 최댓값을 저장해놓고 작은 수부터 2를 곱하기 위해 우선순위큐에 수들을 넣었다. 처음 주어진 최댓값이 우선순위큐에서 나오기 전까지 숫자들을 뽑으면서 2를 곱하고 답을 갱신했다. 메모리: 114588KB시간: 1284ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n.. 2024. 5. 14. [백준] 11000: 강의실 배정 - JAVA https://www.acmicpc.net/problem/11000 풀이수업들의 시작, 종료 시간이 주어지고 강의실을 최소로 배정해야 한다. 수업이 끝나면 해당 강의실을 사용할 수 있다. 수업에 대한 정보를 입력받아 시작 시간을 오름차순으로, 시작 시간이 같다면 종료 시간을 오름차순으로 정렬했다. 우선순위큐에 종료시간을 오름차순으로 담으면서 수업에 대한 정보를 넣어줬다. pq.peek()이 다음 수업의 시작시간보다 작거나 같으면 pq에서 제거해주고 다음 수업을 pq에 넣었다. pq.peek()이 없거나, 다음 수업의 시작시간보다 크다면 answer을 하나 늘려줬다. 메모리: 67960KB시간: 740ms언어: Java 11import java.io.*;import java.util.*;public cl.. 2024. 5. 14. [백준] 1202: 보석 도둑 - JAVA https://www.acmicpc.net/problem/1202 풀이가방의 용량이 정해져있고, 가방에는 보석을 한개씩 넣을 수 있다. 즉, 가방을 오름차순으로 보면서 넣을 수 있는 보석 중 가치가 가장 큰것을 넣으면서 진행한다. 가방을 오름차순으로 정렬하고 가방의 사이즈보다 보석의 무게가 작다면 우선순위큐에 넣고 우선순위큐에서 위의 것을 빼면 되도록 구현했다. 메모리: 115988KB시간: 1888ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int m; int v; public Node(int m, int v) { this.m .. 2024. 5. 14. [백준] 1655: 가운데를 말해요 - JAVA https://www.acmicpc.net/problem/1655 풀이숫자를 입력할 때마다 말했던 숫자들 중 중간값을 말해야한다. PriorityQueue 2개를 사용해 left, right로 저장하고 left의 peek이 항상 중간값이 되도록 구현했다. 따라서, left는 내림차순으로 저장 및 출력했다. left가 비어있거나 left의 peek보다 말한 숫자가 작으면 left에 넣었다. 그렇지 않은 경우는 right에 넣는다. left 크기와 right 크기의 차이가 1보다 크면 left에서 빼서 right에 넣어주고, right의 크기가 더 크면 right에서 빼서 left에 넣어주었다. 즉, left의 크기와 right의 크기의 차이가 0, 1이 되도록 유지했다. 그렇게해서 left의 peek값이 .. 2024. 5. 13. 이전 1 다음