글 읽기 - 우선순위큐 직접구현 반례가 무엇일까요? (go)

leeyjeen 3년 전 0

우선순위큐를 직접 구현하여 풀었습니다.

반례를 찾기 어려워서 문의드립니다. 도움 주시면 감사하겠습니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscanln(reader, &n)
	var heap Heap
	heap.heapArr = make([]uint, n+1)

	for i := 0; i < n; i++ {
		var x uint
		fmt.Fscanln(reader, &x)

		if x == 0 {
			fmt.Fprintln(writer, deleteHeap(&heap))
		} else {
			insertHeap(&heap, x)
		}
	}
}

type Heap struct {
	heapArr   []uint
	numOfData int
}

func deleteHeap(heap *Heap) (delVal uint) {
	if heap.numOfData == 0 {
		return
	}
	delVal = heap.heapArr[1]
	lastVal := heap.heapArr[heap.numOfData]
	var parentIdx int = 1 
	var childIdx int
	for {
		childIdx = parentIdx * 2
		if childIdx > heap.numOfData || heap.heapArr[childIdx] < lastVal {
			break
		}
		if childIdx+1 <= heap.numOfData && heap.heapArr[childIdx] < heap.heapArr[childIdx+1] {
			childIdx++
		}
		heap.heapArr[parentIdx] = heap.heapArr[childIdx]
		parentIdx = childIdx
	}
	heap.heapArr[parentIdx] = lastVal
	heap.numOfData--
	return
}

func insertHeap(heap *Heap, x uint) {
	heap.numOfData++
	var idx = heap.numOfData

	for idx != 1 {
		if x > heap.heapArr[idx/2] {
			heap.heapArr[idx] = heap.heapArr[idx/2]
			idx = idx / 2
		} else {
			break
		}
	}
	heap.heapArr[idx] = x
}

bupjae 3년 전 1

deleteHeap 구현이 불완전합니다.

아래와 같은 데이터를 입력받으면 100 이 제거된 후 51 이 루트로 올라오는데

왼쪽 자식인 50하고만 비교한 채 끝냅니다.

실제로는 오른쪽 자식인 75와 비교한 후 위치를 바꾸어야 합니다.

leeyjeen 3년 전 0

안녕하세요, 말씀해주신 내용 반영하여 deleteHeap 수정 후 통과되었습니다.

중요한 부분을 놓치고 있었네요.

정말 감사드립니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

우선순위큐 직접구현 반례가 무엇일까요? (go)

leeyjeen 3년 전 0

bupjae 3년 전 1

leeyjeen 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말