[CodeKata] 프로그래머스 : 5.21(금), 디스크 컨트롤러

🥋 Oooth More!! (Level 3)

 

🧮 풀이

확실히 3단계에 들어오면서 알아야 할 자료구조도 많다. 이번 우선순위 큐 문제도 그리하여, 모범답안과 함께 개념을 공부하였다.

 

🖇 리뷰

- 풀이

function solution(jobs) {
    var answer = 0;
    jobs.sort((a,b)=>a[0]-b[0]);// 첫 작업은 가장 먼저오는 걸로
    const pq=[];//우선 순위 큐 (시작이 가능한 일들이 들어가며 작업시간 오름차순정렬됨)
    let i=0, time=0;
    while(i<jobs.length || pq.length!=0){// 우선순위큐가 비어야 종료됨
        
        //우선 순위 큐 넣는 작업
        if(i<jobs.length && jobs[i][0]<=time){
           pq.push(jobs[i++]);
           pq.sort((a,b)=>a[1]-b[1]);
           continue;//다음 것도 넣어보러 간다~~
        }
        //현재 도착한 작업이 없을 때
        if(pq.length===0){
            time=jobs[i][0]; //첫 작업을 현재 시간으로 바꿔준다.
        }else{
            const [start,work]=pq.shift();
            answer+=time+work-start;
            time+=work;
        }
        
    }
     
    return parseInt(answer/jobs.length);
}

* 출처 : https://haerang94.tistory.com/328?category=803966/

1. 우선순위 큐를 사용하는 문제이다. 첫 번째 우선순위는 요청시간(0번째 인자)로 sort() 정렬한다.
2. answer는 각 job별로 실행이 완료될 경우, 요청시간부터 완료까지 소요시간을 누적하는 변수다.
3. i는 jobs를 탐색하는 인덱스, time은 시간의 경과를 누적관리하는 변수다. pq는 우선순위 큐 배열이다.
4. pq가 빌 때까지 while 반복문을 순회한다.
5. 우선, jobs를 순회하며 현재 time에서 실행할 수 있는 job들을 pq에 넣는다. 그리고, 작업 소요시간(1번째 인자)가 작은 순서로 우선순위를 다시 정렬한다.
6. pq가 비어있는 경우 현재시간에서 실행할 수 있는 job이 없으므로, time을 실행할 수 있는 가장 빠른 시간으로 바꿔준다.
7. 아니라면, 우선순위가 가장 높은 0번째 요소를 pq에서 shift() 해준다. 이후, time은 작업시간을, answer엔 소요시간을 누적한다.
8. 마지막으로, 누적된 answer를 jobs 길이로 나눈다. 소숫점을 버리므로 parseInt() 혹은 Math.floor() 로 마무리하면 된다.

 

- 개념 : 힙(Heap) & 우선순위 큐(Priority Queue)

 

1. 힙(Heap)

 

힙은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료 구조로, 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성 있는 결과를 도출해내기 위한 자료구조이다.

이 규칙성(대소관계)에 따라, 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나뉜다.

• Heap은 완전 이진트리 형태이다. => 최하단 레벨을 제외한 모든 레벨이 완전히 채워지는 규칙을 의미
• Heap은 트리 내에서 중복된 값을 허용한다.
• Heap은 느슨한 정렬(반 정렬) 상태를 가진다. => 자식노드가 부모 노드보다 무조건 크거나 작다. 하지만, 전체트리에서 가장 아래노드가 가장 크거나 작은 값은 아니라는 의미

 

* 최대 힙(Max Heap) : 부모 노드는 항상 자식 노드보다 크거나 같다.

* 최소 힙(Min Heap) : 부모 노드는 항상 자식 노드보다 작거나 같다.

 

* Heap 인덱싱

• 왼쪽 자식노드 인덱스 = 부모노드 인덱스 * 2 + 1
• 오른쪽 자식노드 인덱스 = 부모노드 인덱스 * 2 + 2
• 부모노드 인덱스 = (자식노드 인덱스 - 1) / 2

 

* Heap 사용 이유

힙은 주로 최소 or 최대값을 O(1)의 시간복잡도로 얻어내기 위해 사용된다.

배열에서 최소/최대값을 탐색한다면, 선형탐색은 O(n), 이진탐색은 O(logn)의 시간복잡도를 보인다.

하지만, 힙은 규칙성으로 노드를 정렬하기에, 최상위 노드에 최소/최대값이 담기게 되므로 0번째 요소를 항상 찾으면 된다.

• 우선순위 큐를 구현하는데 사용한다. (힙과 우선순위 큐는 같은 자료구조가 아니지만, Min Heap은 우선순위 큐 구현에 최적화됨)
• 운영체제에서 우선순위 기반의 일들을 스케쥴링하기 위해 힙을 사용한다.
• 다익스트라 알고리즘(최단거리 알고리즘) 에서 최소비용을 기반으로 탐색할 때 사용된다.

 

* Heap 구현하기 (Min Heap)

 

1) Heap 클래스 선언

class Heap {
  constructor() {
    this.heap = []		// Heap 자료구조가 되는 배열
  }

  // 인덱스 값을 반환하는 메서드들
  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2)
 
  // 최상위 노드 값을 반환하는 메서드
  peek = () => this.heap[0]
}

 

2) Insert 메서드

삽입 매커니즘은 우선 heap 배열 끝에 넣는다. 그런 뒤, Min Heap 규칙성에 따라 위치를 조정한다. (이를, heapifyUp() 메서드가 담당)

class Heap {
  ...

  insert = (key, value) => { // 우선순위를 비교하기 위해서 key, value 로 받는다.
    const node = { key, value } // 객체로 node 를 만들고
    this.heap.push(node) // push 한다.
    this.heapifyUp() // 배열에 가장 끝에 넣고, 다시 min heap 의 형태를 갖추도록 한다.
  }
  
  heapifyUp = () => {
    let index = this.heap.length - 1 // 계속해서 변하는 index 값
    const lastInsertedNode = this.heap[index]

    // 루트노드가 되기 전까지
    while (index > 0) {
      const parentIndex = this.getParentIndex(index)

      // 부모 노드의 key 값이 마지막에 삽입된 노드의 키 값 보다 크다면
      // 부모의 자리를 계속해서 아래로 내린다.
      if (this.heap[parentIndex].key > lastInsertedNode.key) {
        this.heap[index] = this.heap[parentIndex]
        index = parentIndex
      } else break
    }

    // break 를 만나서 자신의 자리를 찾은 상황
    // 마지막에 찾아진 곳이 가장 나중에 들어온 노드가 들어갈 자리다.
    this.heap[index] = lastInsertedNode
  }
}

heapifyUp() 로직은 길지만, 간단히 정리하면 현재 인덱스(heap 배열의 제일 끝) 로부터 부모노드의 인덱스와 값을 탐색한다.

이를 비교해서, 현재 노드가 더 작은 경우 부모노드와 위치를 바꾸면서 이 노드를 위로 올리는 것이다. 이 과정을 break까지 반복한다.

 

3) remove 메서드

삭제 메커니즘은 우선 최상위 노드를 꺼낸다. 그리고, 배열안에 요소가 2개 이상이라면 끝의 노드를 최상위로 올리고 Min Heap 규칙을 적용한다. (마찬가지로, 끌어올려진 부모노드를 내리면서 올바른 위치를 찾는 것을 heapifyDown() 메서드가 담당)

class Heap {
  ...

  remove = () => {
    const count = this.heap.length
    const rootNode = this.heap[0]

    if (count <= 0) return undefined
    if (count === 1) this.heap = []
    else {
      this.heap[0] = this.heap.pop() // 끝에 있는 노드를 부모로 만듬
      this.heapifyDown() 
    }
    return rootNode;		// 우선 최상위 노드를 반환
  }
  
  heapifyDown = () => {
    let index = 0
    const count = this.heap.length
    const rootNode = this.heap[index]

    // 계속해서 left child 가 있을 때 까지 검사한다.
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index)
      const rightChildIndex = this.getRightChildIndex(index)

      // 왼쪽, 오른쪽 중에 더 작은 노드를 찾는다
      // rightChild 가 있다면 key의 값을 비교해서 더 작은 값을 찾는다.
      // 없다면 leftChild 가 더 작은 값을 가지는 인덱스가 된다.
      const smallerChildIndex =
        rightChildIndex < count && this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex

      // 자식 노드의 키 값이 루트노드보다 작다면 위로 끌어올린다.
      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex]
        index = smallerChildIndex
      } else break
    }

    this.heap[index] = rootNode
  }
}

heapifyDown() 은 우선 left child가 있는 동안 계속 검사한다. 이는 곧, 비교할 자식노드가 존재한다는 의미이다.

다음으로, left / right 중 작은 노드(smallerChildIndex)를 찾고, 이것이 현재 루트노드보다 작다면 위치를 바꾸면서 반복한다.

 

2. 우선순위 큐(Priority Queue)

 

우선순위 큐는 일반적인 선입선출(FIFO)이 아닌, 우선순위를 기준으로 삭제한다. (우선순위가 같다면 큐에 삽입된 시점을 기준으로 삭제)

// 위에서 만든 Heap 클래스를 상속
class PriorityQueue extends Heap {
  constructor() {
    super()
  }

  enqueue = (priority, value) => this.insert(priority, value)
  dequeue = () => this.remove()
  isEmpty = () => this.heap.length <= 0
}

• enqueue : Min Heap에 넣기 (주어진 노드들을 순회하면서)
• dequeue : Min Heap에서 빼기 (최상위 노드를 제거하면서 받아오기)
• isEmpty : Heap이 비었는지 체크 (탐색의 종료조건이 될 것)

---

[출처]

 

- 풀이 : https://haerang94.tistory.com/328?category=803966   

- 개념 : https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9