우선순위 큐

[프로그래머스] 숫자 짝꿍 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 우선순위 큐 풀이 X,Y의 최대 길이가 3,000,000 이기 때문에 2중 포문을 이용해 완전탐색으로 짝꿍을 찾으면 3,000,0002 의 연산으로 시간 초과가 발생한다. 따라서 X에서 각 수의 등장횟수를 세고, Y에도 각 수가 등장하면 우선순위 큐에 삽입한다. 이때도, 짝꿍이 최대 3,000,000개가 될 수 있으므로 O(n2)의 시간복잡도를 갖는 Array.sort()를 이용하면 시간초과가 나기 때문에 ArrayList에 담은 후 정렬을 진행하거나 우선순위 큐를 이용해 O(nlogn)의 시간..

[프로그래머스] 체육복 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 그리디, 우선순위 큐 풀이 두 리스트를 오름차순으로 정렬하여 잃어버린 학생마다 남은 체육복 중 번호가 맞는 체육복이 있을 때, 작은 번호의 체육복부터 빌리면 가장 많은 학생이 체육 수업을 들을 수 있다. 1. lost의 원소 중 reserve에 포함된 원소가 있다면 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우이므로 두 리스트에서 해당 원소를 제거하고 체육복을 빌린 학생 수를 나타낼 count를 1 증가시킨다. 2. lost의 리스트를 정렬하고, reserve의 원소들은 우선순위 큐에 삽입..

[백준] 2075. N번째 큰 수 (Java)

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘 우선순위 큐 풀이 모든 수를 리스트에 담은 후 정렬하여 n번째 수를 출력하거나 우선순위 큐를 이용해 정렬하며 삽입하여 n번째 수를 출력한다. 코드 import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.IO..

[백준] 1202. 보석 도둑 (Java)

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 알고리즘 그리디 알고리즘, 정렬, 우선순위 큐 풀이 N과 K가 30만으로 굉장히 크기 때문에 O(n2) 의 미만의 시간 복잡도로 해결해야한다. 이를 위해서 정렬과 우선순위 큐를 사용한다. 준비물 1. 남아있는 보석을 저장할 우선순위 큐 remains (무게 기준 오름차순 정렬) 2. 담을 수 있는 보석을 저장할 우선순위 큐 avails (비용 기준 내림차순 정렬) 3. 가방을 저장할 리스트 bag..

[백준] 1854. K번째 최단경로 찾기 (Java)

문제 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 알고리즘 그래프, 우선순위 큐, 다익스트라(Dijkstra) 알고리즘 풀이 1번 도시에서 다른 모든 도시로 가는 최단 경로를 구해야하므로 다익스트라 알고리즘을 사용한다. 이때 1번째 최단 경로가 아닌 K번째 최단경로를 구하기 위해 각 도시까지의 최단 경로를 담을 n개의 우선순위 큐를 사용한다. 우선순위 큐는 최댓값이 앞에 오도록 구현한다. 이제 해당 도시까지의 새로운 소요시간을 구했을 때 우선순위 큐..

[백준] 1766. 문제집 (Java)

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 알고리즘 위상 정렬, 우선순위 큐 풀이 먼저 푸는 것이 좋은 문제는 반드시 먼저 풀어야한다는 조건이 있다. 즉 문제 사이에 순서가 있으므로 위상 정렬을 사용한다. 또한 각 문제는 쉬운 문제(번호가 작은 문제)부터 풀어야하므로 우선순위 큐를 사용하여 정렬을 유지하면서 큐에서 삭제되는 순서대로 값을 출력하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; imp..

[백준] 15903. 카드 합체 놀이 (Java)

🔒 문제 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 🔑 알고리즘 그리디 알고리즘, 우선순위 큐 (Priority Queue) 💡 풀이 가장 작은 점수를 만드는 방법은 매번 가장 작은 두 수로 카드 합체를 하는 것이다. 따라서 우선순위 큐의 가장 앞에 있는 두 수를 꺼내 카드 합체를 하고 덮어쓴 값을 다시 우선순위 큐에 삽입한다. 시간 복잡도는 O(2*mlogn) 일 것이다. * a 가 최대 100만이므로 합체 과정에서 int 범위를 초과할 수 있어 long 자료형을 사..

[백준] 1715. 카드 정렬하기 (Java)

🔒 문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 🔑 알고리즘 그리디, 우선순위 큐 💡 풀이 10, 20, 40, 30, 50 개의 묶음이 있을 때 어떤 두 묶음을 골라야할까? 비교 횟수가 가장 적은, 즉 두 값의 합이 가장 적은 수를 골라야 비교 횟수뿐만 아니라 두 묶음을 합친 새로운 묶음의 크기도 전체 경우 중 가장 작으므로 다음 비교 횟수를 제일 적게할 수 있는 경우일 것이다. 즉 현재 최적의 선택이 다음 선택에서도 최적임을 보장하는 것이다. 따라서 묶음이 하나가 될 때까지 리스트의..

[백준] 5427. 불 (Java)

🔒 문제 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🔑 알고리즘 BFS, 우선순위 큐 💡 풀이 1초마다 상근이와 불 모두 움직이기 때문에 둘의 상태를 모두 관리해주어야하고, 이제 불이 붙으려는 칸으로 상근이가 이동할 수 없다 (= 불이 상근이보다 먼저 움직인다라)는 조건이 있으므로 우선순위 큐를 이용한 BFS로 문제를 해결했다. 우선순위 큐의 기준을 시간이 빠른 순, 시간이 같다면 type이 낮은 순으로 설정하였고 불은 type을 0으로, 상근이는 type을 1로 설정하여 불이 더 먼저 처리될 수 있게 하였다. *3..

[백준] 1781. 컵라면 (Java)

🔒 문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 🔑 알고리즘 우선순위 큐, 그리디 알고리즘 💡 풀이 N이 최대 20만이므로 시간 복잡도가 O(NlogN)을 넘어가면 시간 초과가 날 것이다. 따라서 순열 등 시간 복잡도가 높은 방법을 사용할 수 없다. 1. 현재 단위 시간과 데드라인이 동일한 문제 중 최대 문제 풀기 문제 번호 1 2 3 4 데드라인 1 1 2 2 컵라면 수 6 7 100 100 해당 방법으로는 위와 같은 상황에서 1,2번 문제를 풀게 되므로 컵라면을 최대로 획득할 수 없다 위 상황에서는 1,2..