힙이란?
힙(Heap)은 완전 이진트리의 일종으로서 일반적으로 root에 최소값이 오는 최소힙과 최대값이 오는 최대힙으로 구분된다.
같은 완전이진트리라 그런지 이진탐색트리와도 비슷한데, 이쪽의 경우 좌우와 상관없이 부모노드가 자식노드보다 작다/크다의 조건만을 갖는 트리이기 때문에 조금 다르다.
이를 일종의 반 정렬상태, 느슨한 정렬상태라고 부르기도 한다.
알고리즘 문제에서, 힙은 주로 우선순위 큐 자료구조를 사용하기 위해 사용된다.
언제 사용할까?
자료구조 끝부분에서 작업이 많다면, 스택을 많이 사용한다.
마찬가지로 PriorityQueue 문제의 경우에도 뭔가 돋보이는 흐름이 존재한다.
그것은 바로
다양한 "시점"에서의 최대값, 혹은 최소값을 요구한다는점.이다.
이 말이 무슨뜻이냐, 하면 사실 PriorityQueue의 존재의의와 관련있다.
만약 모든 값이 비어있거나 다 넣은 후에, 최대값, 최소값을 판별하고 싶다면 PriorityQueue를 사용할 필요가 있을까?
그냥 한바퀴 순회하면서 O(n)으로 찾아버리면 되는데PriorityQueue는 다 담는데만 Nlog(N)의 시간이 필요하다.
PriorityQueue를 사용하는 목적의 핵심은, 바로 삽입작업과 최대/최소값을 꺼내는 작업이, 각각 O(logN), O(1) 밖에 걸리지 않는다는 것이다.
그렇기 때문에 주로 다음과 같은 경우에 Heap, PriorityQueue가 사용된다.
1. 힙에 값을 삽입하는 시간에 따라, 여러 시점으로 나뉘어진다.
2. 각 시점마다 최대값 / 최소값을 요구한다.
3. 위와같은 삽입과, 최대/최소 확인 작업이 엄~청 많이 일어난다.🚀주요 사용하는 기능 in JAVA
PriorityQueue
PriorityQueue pq = new PriorityQueue();힙 문제의 시작이자 끝.
일반 큐처럼 add해주기만 하면 내부적으로 알아서 힙 구조를 만들어준다. 즉 add로 넣고 peek / poll로 확인하고 꺼내기만 하면 된다.
어마어마한 기능에 비해, 굉장히 편리한 자료구조라고 할 수 있을 것 같다.
PriorityQueue (최대 힙)
PriorityQueue pq = new PriorityQueue(new Comparator(){
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});한가지 유의할 점은 일반적으로 PiorityQueue를 선언했을 때, 무조건 최소힙으로 생성된다는 것.
이는 굳이 Integer가 아니라, Comparable 인터페이스를 구현한 다른 요소를 넣어도 마찬가지다.
그렇기 때문에 최대힙을 만들어주고 싶다면 위처럼 Comparator를 직접 구현해서 매개변수로 넣어주던가, 기본 자료형이 아니라면 Comparable 인터페이스로 구현한 compareTo()함수를 알아서 손보면 된다!
더 맵게 (Level 2)
힙 파트의 몸풀기 문제!
모든 음식들을 PriorityQueue에 넣은 후 두 개씩 뽑아서 섞고, 다시 넣어주는걸 반복하면 된다!
import java.util.*;
class Solution {
public int solution(int[] scoville, int K) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int s : scoville) {
pq.add(s);
}
while(pq.peek()<K) {
if(pq.size()<2) {
return -1;
}
int f1 = pq.poll();
int f2 = pq.poll();
pq.add(f1 + f2*2);
answer++;
}
return answer;
}
}라면공장 (Level 2)
쌀이 X톤 남아있다.이 한 문장에 대한 해석이 중요한 문제.
쌀이 X톤 남아있다는 것은, X일 만큼 공급없이 공장을 가동할 수 있다는 뜻이다. 이를 한번 더 해석하면
최소 X일 안에는 쌀을 공급받아야 한다.라는 조건에 이르게 된다.
아하 그렇구나, X일 안의 공급날 중 하나를 정해서 공급받으면 되겠구나!
그렇다면 언제를 선택해야 할까? 문제는 최소한의 횟수로 공급받길 원하고 있다. 최소한의 횟수로 공급하려면, 달리말해 가장 공급량이 많은 날을 선택해야 한다는 뜻으로 해석할 수 있다.
조건의 해석이 끝났으니 이제 코드로 옮기기만 하면 된다.
Priority는 쌀의 공급량. 일 수를 조금씩 늘려가면서 큐에 값을 삽입하고 하나씩 꺼내면서 일 수를 늘려나가면 된다.
전체 쌀의 공급량이 충분해지면, 즉 K보다 많아지면 프로그램을 종료한다.
import java.util.*;
class Solution {
public int solution(int stock, int[] dates, int[] supplies, int k) {
int answer = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
});
int i = 0;
while(stock<k) {
while(i<dates.length && dates[i]<=stock) {
pq.add(supplies[i]);
i++;
}
stock += pq.poll();
answer++;
}
return answer;
}
}디스크 컨트롤러 (Level 3)
드디어 등장한 Level 3 문제.
흐름은 라면공장과 크게 다르지 않다. 앞서 말한 것처럼 문제를 여러 시점으로 나눠서, 각 시점에 대해 반복문을 작성하고, 값을 확인해주면 된다.
이 문제에선 먼저 넣을 수 있는 작업 중, 가장 작업량이 적은 작업을 넣고, 시간이 흐른 후 다시 넣을 수 있는 작업을 큐에 넣어준다.
한가지 중요한 점은, 당장에 PriorityQueue가 비어있더라도, 넣을 작업이 남아있다면, 시간이 흘러야 한다는 것.
그리고 시작시간을 확인하기 위해 Job을 별도의 클래스로 생성해둬야 한다는 것 정도이다.
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
public int solution(int[][] jobs) {
int current = 0;
int idx = 0;
int total = 0;
int len = jobs.length;
Arrays.sort(jobs, new Comparator<>() {
@Override
public int compare(int[] o1, int[] o2) {
// TODO Auto-generated method stub
return o1[0] - o2[0];
}
});
PriorityQueue<Job> pq = new PriorityQueue<>();
while(true) {
while(idx < len && jobs[idx][0] <= current) {
pq.add(new Job(jobs[idx][0], jobs[idx][1]));
idx++;
}
if(pq.isEmpty()) {
if(idx == len){
break;
}else {
current++;
}
}else {
Job j = pq.poll();
current += j.time;
total += current - j.start;
}
}
return total / len;
}
}
class Job implements Comparable<Job>{
int start;
int time;
Job(int start, int time){
this.start = start; this.time = time;
}
@Override
public int compareTo(Job o) {
// TODO Auto-generated method stub
return this.time - o.time;
}
}여담으로 처음 풀 때, 아래 조건을 확인하지 못해서, 더 복잡하고 이상한 코드를 짜고 있었다.
앞으로 문제풀기전에 조건을 꼼꼼히 읽도록하자....💦
하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.이중우선순위큐 (Level 3)
개인적으로 가장 까다로운 문제였다.
우선순위큐를 양방향으로 구현을 해야한다? 가장 먼저 떠오른 방법은 우선순위 큐를 각각 최대힙, 최소힙으로 두 개 구현하는 것이다.
그리고 나서 연산을 코딩하기 위해 시간복잡도를 확인했다.
operations의 길이가 최대 100만, 즉 연산시 모든 값을 훑는 작업은 O(N^2)이 되어 시간초과가 난다.
예를들어 값을 50만개 넣고 50만개 빼는 연산을 한다고 가정하자. 넣는데는 아무 문제 없겠지만, 빼는 작업에서 O(n)짜리 코드를 짜다가는 50만*50만이라는 시간에 걸려서 시간초과가 날 것이다.
결론적으로, 값을 빼는데 O(n) 아래의 시간복잡도를 갖는 코드가 필요하다. 그렇게나 빠른, 자료구조를 생각해봐야 사실 몇 개 없다.
여기서는 HashMap을 이용해보기로 했다. 이전 글에서도 작성했지만, 삽입, 탐색에 있어서 O(1)이라는 시간복잡도를 갖는 사기적인 자료구조다.
아무튼 문제에선 최대힙, 최소힙에 값을 다 넣는 것과 더불어, 각 숫자의 개수에 대해서 HashMap에 저장했다.
만약 최소힙이나 최대힙에서 값을 제거할 때, HashMap에 값이 없다면, 그것은 나머지 한 쪽을 제거할 때 같이 제거되지 못한 이른바 유령 값이다.
만약 유령 값이 발견되면, 무시하고 뽑아버리고 계속 진행하면 된다.
말은 쉽게 했지만, 막상 풀 땐 굉장히 많이 고민했던 문제다.
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
class Solution {
public int[] solution(String[] operations) {
HashMap<Integer, Integer> map = new HashMap<>();
PriorityQueue<Integer> minPq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
});
int size = 0;
for(String oper : operations) {
String[] ops = oper.split(" ");
char command = ops[0].charAt(0);
int number = Integer.parseInt(ops[1]);
if(command == 'I') {
minPq.add(number);
maxPq.add(number);
if(map.containsKey(number)){
map.replace(number, map.get(number)+1);
}else {
map.put(number, 1);
}
size++;
}else {
if(size==0) {
continue;
}else if(number == 1) {
while(!map.containsKey(maxPq.peek())) {
maxPq.poll();
}
int tmp = maxPq.poll();
if(map.get(tmp)==1) {
map.remove(tmp);
}else {
map.replace(tmp, map.get(tmp)-1);
}
}else {
while(!map.containsKey(minPq.peek())) {
minPq.poll();
}
int tmp = minPq.poll();
if(map.get(tmp)==1) {
map.remove(tmp);
}else {
map.replace(tmp, map.get(tmp)-1);
}
}
size--;
if(size == 0) {
minPq = new PriorityQueue<>();
maxPq = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
});
}
}
}
int[] answer = new int[2];
if(size ==0) {
answer[0] = 0; answer[1] = 0;
}else {
while(!map.containsKey(maxPq.peek())) {
maxPq.poll();
}
answer[0] = maxPq.poll();
while(!map.containsKey(minPq.peek())) {
minPq.poll();
}
answer[1] = minPq.poll();
}
return answer;
}
}그런데
다른사람의 풀이를 확인하던 중, 한쪽 큐에서 값을 꺼낼 때마다, 반대쪽 큐에서 해당 값에 remove연산을 사용해서 푸는 코드를 발견했다.
궁금해서 StackOverFlow에 들어가서도 찾아봤지만, remove연산의 시간복잡도는 O(n)이 맞다. 즉 내가 한 계산대로라면 전체 시간복잡도가 O(n^2)가 되어 시간초과가 나야하는데.. 어찌된 일인지, 잘 동작했던 것 같다.
이 부분에 대해서 이유는 아직 밝히지 못했고, 나중에 좀 더 찾아봐야겠다...
