- 제공되는 문제들은 제로베이스 백엔드 스쿨 11기의 비선형 자료구조 문제들입니다.
우선순위 큐의 활용
- 우선순위 큐(Priority Queue) 자료구조는 힙을 사용한 자료구조이다. 힙의 특성상 최대, 최소값만 찾고 나머지는 연산할 필요가 없는 문제들에서 사용될 수 있다.
- 이는 매 턴마다 최대 최소값을 찾기 위해 정렬을 수행해야하는 상황에서 특히 강력함을 발휘할 수 있다.
- 힙 정렬을 사용하여 O(NlogN) 으로 정렬을 수행한다 하더라도 턴의 수가 M인 경우에 전체 시간 복잡도는 O(M x NlogN)으로 M >= N인 상황에서 O(N^2logN)의 수행시간이 걸리며 이는 그렇게 좋은 시간 복잡도는 아니다.
- 이를 우선순위 큐를 통해 최대 - 최소값만을 찾을 경우에 데이터의 삽입 - 삭제만 일어나기 때문에 전체적으로 O(NlogN) 정도로 최대 최소값을 찾을 수 있다.
- 이번에는 몇 가지 문제들을 풀어보면서 우선순위 큐의 활용 방법과 접근 방식을 알아보도록 하자.
1번 문제
- 입력으로 int형 배열 num과 정수 k가 들어온다. 이때, num에서 k 번째로 큰 수를 반환하는 예제를 작성하라는 문제이다.
- 해당 문제는 두 가지 방법으로 풀 수 있는데 우선순위 큐로 최대 힙을 만든 다음 우선순위 큐의 크기가 k를 넘어갈 때 마다 가장 큰 값을 삭제시켜 힙의 루트를 읽어오면 그것이 바로 k 번째로 큰 수가 된다.
- 다른 방법은 정렬을 사용하는 것이다.
import java.util.Arrays;
import java.util.PriorityQueue;
public class Practice1 {
public static int solution1(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int element: nums){
pq.offer(element);
if (pq.size() > k){
pq.poll();
}
}
return pq.peek();
}
public static int solution2(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
public static void main(String[] args) {
// Test code
int[] nums = {3, 1, 2, 7, 6, 4};
System.out.println(solution1(nums, 2));
System.out.println(solution2(nums, 2));
System.out.println();
nums = new int[]{1, 3, 7, 4, 2, 8, 9};
System.out.println(solution1(nums, 7));
System.out.println(solution2(nums, 7));
}
}
- 정렬이 내림차순을 기준으로 정렬되어있음을 유의하자.
2번 문제
문제
- 입력으로 돌의 무게로 이루어진 1차원 배열 stones가 주어진다. 다음의 과정을 거칠 때, 가장 마지막의 돌의 무게를 반환하는 함수를 작성하라.
- stones에서 가장 무게가 큰 돌 2개를 뽑아 충돌시킨다.
- 이때, 돌의 무게가 동일하다면 둘 다 부서져 소멸한다. 그렇지 않을 경우, 두 돌의 무게의 차만큼은 다시 stones에 추가된다.
문제 접근
- 하나의 데이터셋에 가장 큰 두 요소를 뽑고, 그 두 요소간의 차를 다시 데이터셋에 집어넣은 다음 다시 가장 큰 두 요소를 뽑는 연산의 반복을 수행하면서 마지막에 남은 요소의 값을 반환하는 문제이다.
- 해당 문제를 정렬을 통해 수행하려면 다시 집어넣고 다음 두 요소를 찾을 때, 정렬을 또 수행해주어야 한다.
- 문제에서 요구하는 것은 최대값 2개를 요구하는 것이기 때문에 우선순위 큐, 그 중에서 최대 힙을 사용하는데 최적으로 보인다.
import java.util.PriorityQueue;
public class Practice2 {
public static void solution(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
for (int element: stones){
pq.offer(element);
}
while(pq.size() > 1){
int stone1 = pq.poll();
int stone2 = pq.poll();
int diff = stone1 - stone2;
if (diff != 0){
pq.offer(diff);
}
}
System.out.println(pq.peek());
}
public static void main(String[] args) {
// Test code
int[] stones = {2, 7, 4, 1, 8, 1};
solution(stones);
stones = new int[]{5, 3, 5, 3, 4};
solution(stones);
}
}
- 최대 힙의 특성상 stone1 >= stone2임이 자명하므로 diff는 해당 수식으로 고정된다.(무게는 음수로 갈 수 없기 때문)
3번 문제
문제
- 정수들로 이루어진 1차원 배열 nums와 정수 값 k가 입력으로 주어진다. 이때, nums 배열에 주어진 정수들 중 가장 많은 빈도를 가진 숫자들 순으로 k번째 까지 출력하라.
- 동일한 빈도를 가진 경우에 값이 작은 수가 먼저 출력되도록 해야한다.
문제 접근
- 우선순위가 문제에 이미 제시되어 있다. 많은 빈도를 가질 수록 우선순위가 높아지며 동일한 빈도를 가지고 있을 경우에 작은 수가 우선순위가 높다.
- 먼저 각 수가 nums 내에서 얼만큼의 빈도를 가지고 있는지를 먼저 구현해야 한다. 이는 key를 해당 수로, value를 해당 수가 nums에서 등장한 횟수로 정의되는 Map 자료구조를 사용하여 구현할 수 있어 보인다.
- 이후 우선순위 큐의 우선순위를 제시된 우선순위로 설정하여 구현한다.
- 동일한 빈도를 가질 경우, 작은 수가 더 높은 우선순위를 가진다.
- 동일한 빈도를 가지지 않을 경우, 빈도가 더 큰 수가 더 높은 우선순위를 가진다.
- 해당 우선순위 큐에 Map의 데이터들을 넣고 k - 1번만큼 poll하면서 해당 값의 key를 출력하면 마무리된다.
import java.util.*;
public class Practice3 {
public static void solution1(int[] nums, int k) {
if (nums == null){
return;
}
HashMap<Integer, Integer> count = new HashMap<>();
for (int num: nums){
count.put(num, count.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((x, y) -> y.getValue() == x.getValue() ?
x.getKey() - y.getKey() : y.getValue() - x.getValue());
for (Map.Entry<Integer, Integer> element: count.entrySet()){
pq.offer(element);
}
for (int i = 0; i < k; i++){
System.out.print(pq.poll().getKey() + " ");
}
}
public static void main(String[] args) {
// Test code
int[] nums = {1, 1, 1, 2, 2, 3};
solution1(nums, 2);
System.out.println();
nums = new int[]{3, 1, 4, 4, 3, 3, 1, 2, 2, 1, 3};
solution1(nums, 3);
}
}
- 우선순위를 람다 함수를 통해 구현한 것을 잘 살펴보도록 하자.
4번 문제
문제
- 문자열 s가 입력으로 들어온다. 이때, 문자열 내의 동일한 알파벳이 연속으로 배치되지 않도록 문자열을 적절히 재배치하라. 재배치가 가능한 경우 재배치한 문자열을, 그렇지 않다면 null을 반환하라.
| 입력 |
출력 |
| aabb |
abab |
| aaaaabccd |
acadacaba |
| aaca |
null |
문제 접근
- 언듯 보면 우선순위 큐 유형의 문제가 아닌 것 처럼 보인다. 하지만 다음과 같은 방법을 사용함으로서 우선순위 큐를 사용할 수 있다.
- 먼저 각 알파벳이 몇개가 나오는지를 먼저 구해놓는다. aabb의 경우, a 2개, b 2개가 나올 것이다.
- 이제 이를 우선순위 큐에 넣는다. 가장 많은 빈도를 가진 알파벳이 먼저 나오도록 최대 힙을 구성하여 활용한다. aabb의 경우 <a, 2>가 root로 되고, <b, 2>가 그 자식으로 이어져 있는 구조로 될 것이다.
- 이제 우선순위 큐에서 pop하여 재배열한 문자열의 부분 문자로 삽입하고 빈도 수를 1 줄여 다시 힙에 넣어준다. 이때 빈도 수가 0이라면 더 이상 문자열에 해당 알파벳을 붙일 수 없다는 것이므로 힙에 넣으면 안된다.
- 만약 힙이 비어있고, 빼낸 문자의 빈도가 0이 아니라면, 해당 문자가 문자열에 연속적으로 존재한다는 것이 되므로 null을 반환한다.(빼낸 문자는 다시 힙으로 들어가 문자열에 다시 들어간다는 것을 인지하자. 힙이 비어있다면 빼낸 문자가 다시 빠진다는 것을 의미한다.)
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Practice4 {
public static String solution(String s) {
HashMap<Character, Integer> count = new HashMap<>();
for (int i = 0; i < s.length(); i++){
count.put(s.charAt(i), count.getOrDefault(s.charAt(i), 0) + 1);
}
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>((x, y) -> y.getValue() - x.getValue());
for (Map.Entry<Character, Integer> element: count.entrySet()){
pq.offer(element);
}
StringBuilder sb = new StringBuilder();
// 빼낸 문자의 정보를 유지하는 변수
Map.Entry<Character, Integer> prev = null;
while(!pq.isEmpty()){
Map.Entry<Character, Integer> cur = pq.poll();
if (prev != null && prev.getValue() > 0){
pq.offer(prev);
}
sb.append(cur.getKey());
cur.setValue(cur.getValue() - 1);
prev = cur;
// 만약 힙이 비어있고, 빼낸 문자의 빈도가 0이 아니라면 다음 루프에서 빼낸 문자가 다시 들어가게 된다.
// 이는 문제의 제한 조건인 연속된 알파벳이 붙으면 안된다에 위배되므로 null이 반환된다.
if (pq.isEmpty() && prev.getValue() > 0){
return null;
}
}
return sb.toString();
}
public static void main(String[] args) {
// Test code
System.out.println(solution("aabb"));
System.out.println(solution("aaaaabccd"));
System.out.println(solution("aaca"));
}
}