[취업준비일지] - 143

오늘은 이중 우선순위 큐 문제에 도전했다가 처참하게 깨졌다.
토익스피킹을 16시 30분에 치고 집에 오니 18시였는데
대략 3~4시간 끝에 시간초과 엔딩이 되어버렸다.

힙을 두개 사용해서 진행했는데
힙을 사용하는게 아니라 이중연결리스트를 만들고 값을 넣으라는건지
왜 시간초과가 나는지 이해하기 어려웠다..

아래는 오늘 진행한 코드인데 시간복잡도의 문제가 발견되면 제보 바랍니다.

const input = `1
8
I 40
I 42
I 39
I 39
I 41
I 40
D 1
D -1`.split('\n')

const result = []

const getParent = (num) => {
    return Math.floor((num-1)/2)
}

//배열에 push한 다음 index를 저장하고 부모와 비교 후 교체
//while문으로 본인이 더 작은 경우에만 작동
const pushHeap = (heap, pushNum) => {
    let indexNow = heap.length
    heap.push(pushNum)
    while (heap[indexNow] < heap[getParent(indexNow)]) {
        const temp = heap[indexNow]
        heap[indexNow] = heap[getParent(indexNow)]
        heap[getParent(indexNow)] = temp
        indexNow = getParent(indexNow)
    }
}

//0번쨰 인덱스에 저장된 값을 리턴할 필요는 없는 문제고
//마지막 인덱스의 값을 pop해서 0번째에 넣어준 다음
//해당 인덱스에서 자식 인덱스들과 비교해 더 작은 숫자가 있는 경우
//둘 중 더 작은 숫자와 교체하고 그 위치에서 계속 자식과 비교
//생각해보니 값을 리턴해줘야 반대편 힙에서 제거해야 할 숫자를 알 수 있다.
const popHeap = (heap) => {
    const popedValue = heap[0]
    if(heap.length > 1){
        let indexNow = 0
        heap[indexNow] = heap.pop()
        while(heap[indexNow] > heap[indexNow*2 +1] || heap[indexNow] > heap[indexNow*2 +2]){
            const temp = heap[indexNow]
            if(heap[indexNow*2 +1] > heap[indexNow*2 +2]){
                heap[indexNow] = heap[indexNow*2 +2]
                heap[indexNow*2 +2] = temp
                indexNow = indexNow*2 +2
            }
            else{
                heap[indexNow] = heap[indexNow*2 +1]
                heap[indexNow*2 +1] = temp
                indexNow = indexNow*2 +1
            }
        }
    }
    else{
        heap.pop()
    }
    return popedValue
}

//다른 힙에서 제거된 값의 위치에 마지막 인덱스의 값을 넣고
//해당 값을 계속 자식들과 비교해가며 위치를 바꿔주기(pop과 유사작업)
const deletHeap = (heap, deleteValue) => {
    let indexNow = heap.indexOf(deleteValue)
    if(indexNow === heap.length-1){
        heap.pop()
        return
    }
    heap[indexNow] = heap.pop()
    
    while(heap[indexNow] > heap[indexNow*2 +1] || heap[indexNow] > heap[indexNow*2 +2]){
        const temp = heap[indexNow]
        if(heap[indexNow*2 +1] > heap[indexNow*2 +2]){
            heap[indexNow] = heap[indexNow*2 +2]
            heap[indexNow*2 +2] = temp
            indexNow = indexNow*2 +2
        }
        else{
            heap[indexNow] = heap[indexNow*2 +1]
            heap[indexNow*2 +1] = temp
            indexNow = indexNow*2 +1
        }
    }
}

for(let i = 1 ; i < input.length ; i++){
    const amount = Number(input[i])
    const maxHeap = []
    const minHeap = []
    
    for(let j = i+1 ; j <= i+amount ; j++){
        const [order, nums] = input[j].split(' ')
        if(order === "I"){
            pushHeap(minHeap, BigInt(nums))
            pushHeap(maxHeap, BigInt(nums)*-1n)
        }
        else if(nums === "1" && maxHeap.length){
            const popedNum = popHeap(maxHeap) * -1n
            deletHeap(minHeap, popedNum)
        }
        else if(nums === "-1" && maxHeap.length){
            const popedNum = popHeap(minHeap) * -1n
            deletHeap(maxHeap, popedNum)
        }
    }
    
    if(maxHeap.length > 0){
        result.push(`${String(popHeap(maxHeap)) * -1} ${popHeap(minHeap)}`)
    }
    else{
        result.push("EMPTY")
    }
    i += amount
}
console.log(result.join('\n'))


//1.최소 힙 구현
//값 추가 시 배열의 마지막에 추가 후 부모와 비교
//값 제거 시 index 0에서 꺼낸 다음 마지막 값 넣고 비교
//2.최대 힙 구현?
//입력 및 출력값 *-1로 최소힙 함수 사용
//3.특정 값 제거 및 힙 최소힙 유지 함수 생성
//indexOf로 찾은 index값을 기준으로 마지막 값을 넣고 값 제거 while문과 동일하게 사용
//4.heap의 길이가 0일경우 pop 무시
//5.최종 결과물 길이가 0인지 판별 후 출력

(1).백준 2914 저작권은 저작권이 있는 멜로디의 갯수를 구하는 문제로
앨범 숫자 * 평균 곡 숫자 - 앨범 숫자 + 1을 통해 해결할 수 있었다.

간단한 수학 관련 문제로 알고리즘이 관계가 있는지는 이해할 수 없었다.
4시간동안 문제 해결이 되지 않아 출석용으로 푼 문제다.

const [amount, average] = `38 24`.split(' ').map(Number)
console.log(amount*average - amount + 1)