우선순위 큐19 [백준] 11000번 - 강의실 배정 [Java] https://www.acmicpc.net/problem/11000 1. 아이디어 그리디 알고리즘으로 해결할 수 있었다.시작 시간에 대한 오름차순 정렬 우선순위 큐와 종료 시간에 대한 오름차순 우선순위 큐 두 개를 활용해서 해결할 수 있다.2. 문제풀이 시작 시간에 대한 오름차순 우선순위 큐를 items, 종료 시간에 대한 오름차순 우선순위 큐를 pq로 선언했다.pq에 items의 첫번째 원소를 삽입한채로 시작하며 pq의 peek의 종료 시간보다 items의 peek의 시작 시간이 늦으면 pq의 해당 강의 뒤에 items의 강의를 붙이는 개념으로 생각할 수 있어서 pq의 해당 원소를 제거했다.pq에서 제거했으면 뒤에 붙이는 거니 pq에 삽입해야하고 pq에서 제거하지 않았어도 새로운 강의실이 필요한 것이.. 2025. 3. 6. [백준] 2457번 - 공주님의 정원 [Java] https://www.acmicpc.net/problem/2457 1. 아이디어 그리디 알고리즘으로 해결할 수 있었다.시작일에 대한 오름차순 정렬 우선순위 큐와 종료일에 대한 내림차순 우선순위 큐 두 개를 활용해서 3월 1일부터 피어있는 꽃 중 가장 지는 날이 늦을 꽃을 선택하고 현재 날짜를 갱신 후 다시 현재 날짜에 피어 있는 꽃 중 가장 지는 날이 늦은 꽃을 선택하는 과정을 반복했다.2. 문제풀이 최초 모든 꽃은 시작일에 대한 오름차순 우선순위 큐에 담았다.이후 현재 날짜를 3월 1일로 세팅해서 3월 1일에 피어져 있는 꽃들을 임시 우선순위 큐에 담고 이 중 가장 지는 날이 늦은 꽃 하나만 선택했다. 이후 현재 날짜를 다시 갱신하고 현재 날짜 기준 피어져 있는 꽃들을 다시 임시 우선순위 큐에 담는 .. 2025. 3. 5. [백준] 14696번 - 딱지놀이 [Java] https://www.acmicpc.net/problem/14696 1. 아이디어 내림차순으로 정렬하는 우선순위 큐를 활용해서 남은 딱지 중 가치가 높은 딱지를 비교하는 과정을 반복해서 해결했다.2. 문제풀이 딱지놀이는 가진 딱지 중 가장 가치가 높은 딱지를 비교해서 동일하면 두번째로 가치가 높은 딱지를 비교하는 과정을 반복한다. 각 딱지를 내림차순 우선순위 큐에 넣어서 반복 비교를 하는 방식으로 구현했고 딱지가 먼저 떨어진 쪽이 지는 점과 동시에 딱지가 다 떨어지면 비기는 것을 같이 반복문으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws I.. 2025. 2. 12. [백준] 2696번 - 중앙값 구하기 [Java] https://www.acmicpc.net/problem/2696 1. 아이디어 중앙값보다 작은 수들을 모은 우선순위 큐와 중앙값보다 큰 수들을 모은 우선순위 큐를 활용하면 해결할 수 있다.2. 문제풀이 중앙값보다 작은 수들을 모은 우선순위 큐는 내림차순 정렬, 중앙값보다 큰 수들을 모은 우선순위 큐는 오름차순 정렬을 해서 두 우선순위 큐의 peek 값이 중앙값 바로 전후가 되도록 했다. 이후 두 우선순위 큐의 크기를 동일하게 유지만 하면 간단하게 중앙값을 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 12. [백준] 1655번 - 가운데를 말해요 [Java] https://www.acmicpc.net/problem/1655 1. 아이디어 오름차순으로 정렬하는 우선순위 큐와 내림차순으로 정렬하는 우선순위 큐 두 개를 활용해서 해결할 수 있다. 내림차순으로 정렬하는 우선순위 큐의 peek에 중간값이 위치하게 하면 된다.2. 문제풀이 두 큐의 원소가 같거나 내림차순으로 정렬하는 우선순위 큐가 하나 더 많은 상태를 계속 유지하면서 내림차순으로 정렬하는 우선순위 큐의 peek 값을 출력하면 된다. 이때 내림차순으로 정렬하는 우선순위 큐의 peek 값이 오름차순으로 정렬하는 우선순위 큐의 peek 값보다 항상 작거나 같게 해주면 됐다.3. 코드 import java.io.*;import java.util.*;public class Main { public sta.. 2025. 2. 11. [백준] 1781번 - 컵라면 [Java] https://www.acmicpc.net/problem/1781 1. 아이디어 그리디 알고리즘으로 해결할 수 있다.현재 날짜를 N일부터 1일까지 이동하며 해당 일에 풀 수 있는 문제 중 가장 컵라면을 많이 받는 문제들을 푸는 과정을 반복하면 된다.2. 문제풀이 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐와 컵라면 수에 대해 내림차순으로 정렬하는 우선순위 큐를 사용했다.입력을 받아 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐에 담은 후 for문으로 각 날짜에 대해 해당 날짜에 풀었을 때 컵라면을 받을 수 있는 문제들을 데드라인에 대해 내림차순으로 정렬하는 우선순위 큐에서 컵라면 수에 대해 내림차순으로 정렬하는 우선순위 큐로 옮겼다.3. 코드 import java.io.*;import .. 2025. 2. 11. [백준] 1202번 - 보석 도둑 [Java] https://www.acmicpc.net/problem/1202 1. 아이디어 그리디 알고리즘으로 해결할 수 있다.가방들을 크기가 작은 순으로 정렬한 후 각 가방에 담을 수 있는 무게의 보석들 중 가장 가격이 높은 보석을 담는 과정을 반복하면 된다.2. 문제풀이 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐와 보석의 가격에 대해 내림차순으로 정렬하는 우선순위 큐를 사용했다.입력을 받아 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐에 담은 후 각 가방에 대해 해당 가방에 담을 수 있는 무게의 보석들을 보석의 무게에 대해 오름차순으로 정렬하는 우선순위 큐에서 보석의 가격에 대해 내림차순으로 정렬하는 우선순위 큐로 옮겼다.3. 코드 import java.io.*;import java.u.. 2025. 2. 11. [백준] 13975번 - 파일 합치기 3 [Java] https://www.acmicpc.net/problem/13975 1. 아이디어 두 파일을 합치는 과정을 반복할 때 작은 두 파일을 합치는 과정을 반복해야 최소 비용으로 하나의 파일로 만들 수 있다. 이를 위해 우선순위 큐를 활용했다.2. 문제풀이 우선순위 큐에 초기 파일들을 담은 후 두 파일을 꺼내서 합친 후 다시 우선순위 큐에 넣는 과정을 반복했다. int형 오버플로우가 발생할 수 있음에 주의해야 한다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea.. 2025. 2. 11. [백준] 1715번 - 카드 정렬하기 [Java] https://www.acmicpc.net/problem/1715 1. 아이디어 카드를 합쳐나가서 하나의 카드 묶음이 될 때까지 반복하는 문제로 숫자가 작은 카드 묶음을 반복해서 더할수록 효율적이다. 우선순위 큐를 활용하면 간단하게 정렬해서 해결할 수 있다.2. 문제풀이 우선순위 큐에 초기 카드 묶음을 담은 후 두 묶음을 빼서 더한 후 다시 우선순위 큐에 넣는 과정을 반복했다. 이렇게 하면 작은 카드 묶음이 반복적으로 더해져서 최소 비교 횟수로 하나의 묶음으로 만들 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2025. 2. 11. [백준] 2075번 - N번째 큰 수 [Java] https://www.acmicpc.net/problem/2075 1. 아이디어 우선순위 큐를 활용하면 간단하게 해결할 수 있다.2. 문제풀이 N개의 수를 우선순위 큐에 담은 후 N * N - N개의 수는 하나를 담고 우선순위 큐에서 하나를 뺐다. 그러면 가장 큰 N개의 수가 우선순위 큐에 남게 되고 여기서 하나를 빼면 N번째로 큰 수가 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in).. 2025. 2. 11. [백준] 16236번 - 아기 상어 [Java] https://www.acmicpc.net/problem/16236 1. 아이디어 우선순위 큐와 BFS를 활용한 시뮬레이션으로 해결할 수 있다.2. 문제풀이 아기 상어와 관련된 정보인 위치와 크기는 static 변수로 관리하며 BFS 알고리즘을 적용했다. 아기 상어의 위치를 입력 받으면 해당 정보로 초기화를 하고 공간에서 아기 상어의 표시인 9를 빈칸인 0으로 변경해서 이후 탐색이 용이하게 했다. 시뮬레이션은 무한 루프에서 BFS를 적용해서 엄마 상어에게 도움을 요청하는 표시인 -1을 반환하면 종료하고 아니면 누적 시간을 더하고 먹은 물고기를 세줬다. 먹은 물고기 수가 아기 상어의 크기와 같아지면 아기 상어의 크기를 키우고 먹은 물고기 수를 0으로 초기화했다. BFS는 아기 상어가 물고기를 먹는 조건이.. 2025. 2. 10. [백준] 1766번 - 문제집 [Java] https://www.acmicpc.net/problem/1766 1. 아이디어 위상 정렬과 우선순위 큐를 활용하면 해결할 수 있다.2. 문제풀이 위상 정렬만으로 조건 1과 조건 2는 만족할 수 있는데 조건 3이 안될 수가 있다. 위상 정렬의 Queue에 있는 원소들은 모두 동일한 단계이므로 Queue를 우선순위 큐로 바꾼 위상정렬을 적용하면 조건 3도 만족시킬 수 있었다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR.. 2025. 2. 3. 이전 1 2 다음
