[Algorithm] 프로그래머스 - 이중우선순위큐 (힙 - Heap )

 

 

프로그래머스 문제입니다.

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

 

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

---

제한사항

 

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

---

입출력 

---

입출력 설명

예제 #1

- 16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
- 7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

---

문제풀이

function solution(operations) {
    let numbers = []
    // (1)
    operations.forEach(operation => {
        // (2)
        const items = operation.split(" ")
        // (3)
        if (items[0] === "I") {
            numbers.push(Number(items[1]))
        // (4)
        } else if ( items[0] === "D" && numbers.length !== 0){
            numbers.splice(numbers.findIndex(data => {
                return data === (items[1] === '1' ? Math.max(...numbers) : Math.min(...numbers))}), 1)
        }
    })
    // (5)
    return numbers.length !== 0 ? [Math.max(...numbers), Math.min(...numbers)] : [0, 0]
}

 

idea: operation마다 loop을 돌면서 최대, 최소값을 빼주거나 데이터를 푸시

(1) operations 배열마다 loop를 돌 수 있게, forEach를 사용(es6)

(2) operation에서 공백을 기준으로 나눈다.

   첫 번째가 커맨드, 두 번째가 데이터가 된다.

    ex) "I 16" => ["I", "16"]

(3) I라면 데이터를 numbers에 푸시!

(4) numbers 배열의 요소가 존재하고, D 커맨드일 때,

     data가 1이라면 number의 max 값의 인덱스를 찾아서 잘라낸다.

     data가 -1이라면 number의 min 값의 인덱스를 찾아서 잘라낸다.

(5) numbers 배열이 존재한다면, [max, min]을 그렇지 않다면 [0, 0]을 리턴한다.