프로그래머스의 [Lv.3 야근 지수] 문제다.
남은 일의 최댓값을 하나씩 줄여나가면 된다고 생각해서, 반복문을 돌며 최대값을 찾아 1씩 빼는 함수를 만들었다.
function solution(n, works) {
works.sort((a, b) => b - a);
while (n) {
if (works[0] < works[1]) works.sort((a, b) => b - a);
if (!works[0]) break;
works[0] -= 1;
n--;
}
return works.reduce((acc, cur) => {
return acc + Math.pow(cur, 2);
}, 0);
}계속해서 sort() 해줘야 하기 때문에 효율성이 굉장히 떨어지리라고 짐작은 했지만, 제출해 보니 역시나 효율성 부분에서 실패했다.
JavaScript sort() 메서드는 크롬의 v8 엔진 기준 팀 정렬(Tim sort)를 사용한다. 이는 병합 정렬(Merge sort)와 삽입 정렬(Insert sort)을 결합하여 만든 정렬이다. JavaScript뿐만 아니라 Python, swift 등의 많은 언어에서 표준 정렬 알고리즘으로 사용되고 있다.
최고: O(n)
평균: O(n log n)
최악: O(n log n)
하지만 아무리 기존의 알고리즘들의 단점을 보완해서 만들었다고 한들, 엄청난 반복문 속에서의 sort()는 여전히 무리다. 그래서 찾아본~ 우선순위 큐!
우선순위 큐(Priority queue)
우선순위큐는 보통 힙이나 이진 탐색 트리로 구현된다. 둘 다 이진 트리 구조라는 공통점이 있지만, 정렬 방식이 조금 다르다.
이진 탐색 트리(Binary Search Tree)
- 구조
왼쪽 서브 트리와 오른쪽 서브트리의 정렬로 이루어짐 - 정렬 방식
좌 자식 노드 < 부모 노드 < 우 지식 노드 (최댓값은 우 최하단, 최솟값은 좌 최하단) - 시간 복잡도
평균적으로 O(log n), 하지만 최악의 경우 O(n) - 용도
데이터의 정렬된 저장 및 검색이 필요한 경우 사용 - 중복값
허용
이진 탐색 트리는 최댓값과 최솟값이 트리의 최하단 양 끝에 위치하기 때문에, 이를 찾아서 사용하고 다시 정렬하기에는 무리가 있다. 우리는 최댓값을 계속 찾아야 하기 때문에 이진 힙을 사용한 우선순위 큐를 만들어서 사용해야 한다. 그렇다면 이진 힙에 대해 자세히 알아보자.
이진 힙(Binary heap)
힙은 완전 이진 트리다. 완전 이진 트리는 새로운 노드를 추가할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리를 말한다.
- 정렬 방식
최대힙 : 부모 노드 > 자식 노드 (자식간의 크기는 상관 없음)
최소힙 : 부모 노드 < 자식 노드 (자식간의 크기는 상관 없음) - 시간 복잡도
최대/최소값 탐색 O(1), 삽입 및 삭제 O(log n) - 용도
최대, 최솟값을 빠르게 탐핵하기 위함 - 중복값
허용 X
힙은 최대힙(Max tree)과 최소힙(Min tree)로 나뉜다. 최대힙은 최상단 노드에 최댓값이 위치하고, 최소힙은 최상단 노드에 최솟값이 위치한다. 때문에 데이터의 최대/최솟값을 탐색할 때의 시간 복잡도가 무려 O(1)이다! 데이터를 우선순위에 따라 관리하고, 높은 우선순위의 요소를 빠르게 추출하기 위해 사용된다.
구현
이진 힙은 1차원 배열로 구현하며, 1번째 인덱스부터 시작한다. 때문에 클래스 생성자에 다음과 같은 변수를 선언해줬다.
class MaxHeap {
constructor() {
this.heap = [null];
}
}다음으로 필요한 것은 각 노드의 부모 인덱스와 자식 인덱스를 구하는 함수다. 일차원 배열에서 어떻게 트리를 구현할까?
- 왼쪽 자식의 index =
부모 index * 2 - 오른쪽 자식의 index =
(부모 index * 2) + 1 - 부모의 index =
Math.floor(자식의 인덱스 / 2)
해당 공식을 통해서 부모노드와 자식노드를 구하는 함수를 추가해준다.
getParentIdx(idx) {
return Math.floor(자식의 인덱스 / 2);
}
getChildIdx(idx) {
return [idx * 2, idx * 2 + 1];
}다음은 두 노드의 값을 바꿔주는 함수다.
swap(idx1, idx2) {
[this.heap[idx1], this.heap[idx2]] = [this.heap[idx2], this.heap[idx1]];
}그 다음은~~ 값이 삽입하고 삭제하는 함수를 구현해야 한다. 삽입은 다음과 같은 순서로 진행된다.
삽입
1. 트리 최하단의 가장 왼쪽에 값을 추가한다.
2. 해당 노드와 부모 노드의 값을 비교해 정렬이 되어있다면 멈춘다.
3. 아니라면 두 노드의 위치를 바꿔주고, 2번부터 반복한다.
즉, 마지막 노드에 값을 추가하고 위로 끌어올리면서 정렬한다.
push(n) {
this.heap.push(n);
let curIdx = this.heap.length - 1;
let parIdx = this.getParentIdx(curIdx);
while (curIdx > 1 && this.heap[parIdx] < this.heap[curIdx]) {
this.swap(parIdx, curIdx);
curIdx = parIdx;
parIdx = this.getParentIdx(curIdx);
}
}값의 삭제는 삽입과 반대다. 루트 노드를 삭제한 뒤 해당 자리에 힙의 마지막 노드 값을 넣는다. 그리고 자식 노드와 값을 비교하며 위에서 아래로 끌어내리는 방식으로 정렬한다.
삭제
1. 루트 노드를 삭제한다. (최댓값 또는 최솟값)
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 해당 노드와 자식 노드의 값을 비교해 정렬이 되어있다면 멈춘다.
4. 아니라면 두 노드의 위치를 바꿔주고, 3번부터 반복한다.
shift() {
const max = this.heap[1];
if (this.heap.length <= 2) this.heap = [null];
else this.heap[1] = this.heap.pop();
let curIdx = 1;
let [leftIdx, rightIdx] = this.getChildIdx(curIdx);
if (!this.heap[leftIdx]) return max;
if (!this.heap[rightIdx]) {
if (this.heap[leftIdx] > this.heap[curIdx]) {
this.swap(leftIdx, curIdx);
}
return max;
}
while (
this.heap[leftIdx] > this.heap[curIdx] ||
this.heap[rightIdx] > this.heap[curIdx]
) {
const maxIdx =
this.heap[leftIdx] < this.heap[rightIdx] ? rightIdx : leftIdx;
this.swap(maxIdx, curIdx);
curIdx = maxIdx;
[leftIdx, rightIdx] = this.getChildIdx(curIdx);
}
return max;
}다시 문제로...
이렇게 구현한 최대힙을 사용한다면 이 문제는 어렵지 않게 풀 수 있다.
function solution(n, works) {
const maxHeap = new MaxHeap();
works.forEach((el) => maxHeap.push(el));
for (let i = n; i > 0; i--) {
const maxWork = maxHeap.shift();
if (maxWork === 0) break;
maxHeap.push(maxWork - 1);
}
return maxHeap.heap.reduce((acc, cur) => acc + cur ** 2);
}최대힙에 모든 값을 넣어준 뒤, 일할 수 있는 양 만큼 반복문을 돌면서 최대로 많이 남은 일을 1씩 빼줫다. 1을 빼줄 때마다 sort()를 하지 않아도 되기 때문에 효율이 훨~씬 좋다!
