프로그래머스 이중우선순위큐

 

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

<문제 핵심>

1. 문제의 카테고리가 '힙'이긴 하지만 힙 자료구조를 안 써도 풀 수 있는 문제로 파악하였다. 시간복잡도 면에서는 안 좋은 풀이 같은데 다른 풀이로도 한번 풀어봐야겠다.!  구글링 해서 다른 사람들의 후기를 보니까 해당 문제가 리뉴얼된다면 해당 코드는 틀릴 수도 있을 것 같다.(만약 힙 자료구조를 안 쓰면 틀리도록 리뉴얼 된다면)

 

<문제 풀이과정 및 순서도>

1. operations를 배열로 만든 각 명령어에 따라서 로직을 구현한다.

✅ D 같은 경우 D 1 or D -1 으로 나누어지는데 숫자가 1이냐 아니냐에 따라서 힙에 있는 요소들 중 최대값 혹은 최소값을 찾는다. 찾은 값의 인덱스 까지 찾은 다음 힙에서 제거해주면 답을 구할 수 있다. 

function solution(operations) {
    const heap = [];
    const op = operations.map((operation) => operation.split(" "));
  	// 입력된 명령어를 공백(' ')을 기준으로 분할한다.
  	// 따라서 배열[0]은 명령어 배열[1]은 숫자로 구분 가능
    
    op.forEach(num => {
        if(num[0] === 'I') {	// 명령어가 I라면 주어진 숫자 삽입하기
            heap.push(Number(num[1]))
        }
        else {	// 명령어가 D인 경우는 D 1 or D -1로 나누어짐
            const findValue = (num[1] === '1' ? Math.max : Math.min)(...heap);
          	// 숫자가 1이라면 max값을, -1이라면 min값을 적용해서
            const delIdx = heap.indexOf(findValue);
          	// 찾고자 하는 값의 인덱스를 찾아서
            heap.splice(delIdx, 1);
          	// (이름만 heap인) 배열에서 해당 인덱스의 원소를 제거
        }
    })
    
    return heap.length ? [Math.max(...heap), Math.min(...heap)] : [0, 0];
}

 

<전체 코드>

function solution(operations) {
    const heap = [];
    const op = operations.map((operation) => operation.split(" "));
  	// 입력된 명령어를 공백(' ')을 기준으로 분할한다.
  	// 따라서 배열[0]은 명령어 배열[1]은 숫자로 구분 가능
    
    op.forEach(num => {
        if(num[0] === 'I') {	// 명령어가 I라면 주어진 숫자 삽입하기
            heap.push(Number(num[1]))
        }
        else {	// 명령어가 D인 경우는 D 1 or D -1로 나누어짐
            const findValue = (num[1] === '1' ? Math.max : Math.min)(...heap);
          	// 숫자가 1이라면 max값을, -1이라면 min값을 적용해서
            const delIdx = heap.indexOf(findValue);
          	// 찾고자 하는 값의 인덱스를 찾아서
            heap.splice(delIdx, 1);
          	// (이름만 heap인) 배열에서 해당 인덱스의 원소를 제거
        }
    })
    
    return heap.length ? [Math.max(...heap), Math.min(...heap)] : [0, 0];
}