백준77 백준 31860: 열심히 일하는 중(java) 문제풀이 우선순위 큐를 이용하는 문제다.PriorityQueue queue=new PriorityQueue(Comparator.reverseOrder());우선순위 큐 queue를 생성하되, 중요도가 높은 일부터 먼저 처리하게끔 해야 하므로 Comparator.reverseOrder()를 지정해야 한다. 이후 queue에서 poll한 값을 K와 비교해 K 이하일 경우 삭제된 채로 continue하고, K 초과일 경우 이 값에서 M만큼 뺀 값을 다시 queue에 삽입한다. 위 과정을 queue가 공백 상태가 될 때까지 반복하고, 한 번 반복할 때마다 count를 1씩 증가시킨다.import java.io.BufferedReader;import java.io.IOException;import java.io.. 2024. 8. 25. 백준 28107: 회전초밥(java) 문제풀이 손님 큐와 초밥 큐, 2개의 우선순위 큐를 이용해 풀이한다. customer 우선순위 큐에 { 초밥 종류, 손님 번호 }를 원소로 가지는 배열을 삽입한 후 초밥 종류에 따라 오름차순으로 정렬하고, 같은 종류의 초밥일 경우 손님 번호 순으로 정렬한다.PriorityQueue customer=new PriorityQueue(new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[0]==o2[0]) { //같은 초밥일 경우 return o1[1]-o2[1]; //손님 순서로 정렬 } return o1[0]-o2[0]; //초밥 종류로 정렬 }}); 이때 Comparator 수정을 통해 정렬 규칙을 추가해 .. 2024. 8. 25. 백준 11286: 절댓값 힙(java) 문제풀이 작은 수부터 출력해야 하므로 최소 우선순위 큐로 풀이하되, 절댓값은 같지만 부호가 다를 경우 순서를 조정해야 하므로 Comparator를 수정한다.class NewComparator implements Comparator{ @Override public int compare(Integer o1, Integer o2) { if(Math.abs(o1)>Math.abs(o2)) { //o1의 절댓값이 더 크면 자리 변경 return Math.abs(o1)-Math.abs(o2); } else if(Math.abs(o1)==Math.abs(o2)) { //절댓값이 동일하면 음수를 앞으로 보냄 return o1-o2; } else { return -1; .. 2024. 8. 24. 백준 23757: 아이들과 선물 상자(java) 문제풀이 우선순위 큐를 사용해 쉽게 해결할 수 있다. 선물이 가장 많이 담겨있는 상자부터 열어야 하므로 최대 우선순위 큐를 사용하고, PriorityQueue 객체 생성 시 내림차순 정렬을 위해 Comparator.reverseOrder()을 지정한다. 누군가 선물을 가져갔던 상자에서 또다시 가져가도 된다는 점에만 주의하면 된다. 원하는 만큼(n) 선물을 가져간 후(poll) 남은 상자는 다시 정렬에 포함시켜야 하므로(add) 아래와 같이 작성할 수 있다.queue.add(queue.poll()-n); 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Co.. 2024. 8. 24. 백준 2075: N번째 큰 수(java) 문제풀이 우선순위 큐를 이용하면 쉽게 풀 수 있다. N*N개의 수를 모두 우선순위 큐에 삽입하고 (N-1)개의 요소를 삭제한 뒤 N번째 요소를 출력하면 된다.N번째로 큰 수를 출력해야 하므로 최대 우선순위 큐를 사용하고, 이를 위해 PriorityQueue 객체 생성 시 Comparator.reverseOrder()를 지정해야 함에 주의하자. 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main .. 2024. 8. 24. 백준 11279: 최대 힙(java) 문제풀이 최대 우선순위 큐를 이용하는 문제이다. PriorityQueue 객체 생성 시 내림차순 정렬하는 것을 제외하면 1927번 문제와 풀이 방식이 동일하다. 내림차순 정렬을 위해 Comparator.reverseOrder()을 사용한다.PriorityQueue queue=new PriorityQueue(Comparator.reverseOrder()); 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Comparator;import java.util.PriorityQueue;public class Main { public static void main(.. 2024. 8. 24. 이전 1 ··· 3 4 5 6 7 8 9 ··· 13 다음
