글 읽기 - 1655번 질문합니다. 너무 답답하네요 도와주세요...

(追記) (追記ここまで)

1655번 질문합니다. 너무 답답하네요 도와주세요...

1655번 - 가운데를 말해요

rhrudwnszoq 1년 전 1

하루종일 우선순위 큐에대해서 공부하고 최소힙, 최대힙 구현해서 문제를 풀었는데

어디서 틀렸는지를 도저히 모르겠습니다.

몇번 리팩터링해서 당연히 될거라고 생각하는데 자꾸안되네요...

프로그래머스처럼 어디가 틀렸는지 반례가 확인되면은 모를까 너무 답답하네요

문제가 무엇일까요? 제가생각했을때 반드시 통과해야하는데 원인을 모르겠습니다.

const INPUT_PATH = "./inputs/가운데를_말해요.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : INPUT_PATH;
const input = require("fs")
	.readFileSync(filePath)
	.toString()
	.trim()
	.split("\n")
	.map(Number);
class Heap {
	constructor() {
		this.items = [];
	}
	swap(index1, index2) {
		let temp = this.items[index1];
		this.items[index1] = this.items[index2];
		this.items[index2] = temp;
	}
	parentIndex(index) {
		return Math.floor((index - 1) / 2);
	}
	leftChildIndex(index) {
		return index * 2 + 1;
	}
	rightChildIndex(index) {
		return index * 2 + 2;
	}
	parent(index) {
		return this.items[this.parentIndex(index)];
	}
	leftChild(index) {
		return this.items[this.leftChildIndex(index)];
	}
	rightChild(index) {
		return this.items[this.rightChildIndex(index)];
	}
	size() {
		return this.items.length;
	}
	peek() {
		return this.items[0];
	}
}
class MinHeap extends Heap {
	bubbleUp() {
		let index = this.items.length - 1;
		while (
			this.parent(index) !== undefined &&
			this.parent(index) > this.items[index]
		) {
			this.swap(index, this.parentIndex(index));
			index = this.parentIndex(index);
		}
	}
	bubbleDown() {
		let index = 0;
		while (
			this.leftChild(index) !== undefined &&
			this.leftChild(index) < this.items[index]
		) {
			let smallerIndex = this.leftChildIndex(index);
			if (
				this.rightChild(index) !== undefined &&
				this.rightChild(index) < this.items[index]
			) {
				if (this.rightChild(index) < this.leftChild(index)) {
					smallerIndex = this.rightChildIndex(index);
				}
			}
			this.swap(index, smallerIndex);
			index = smallerIndex;
		}
	}
	add(item) {
		this.items[this.items.length] = item;
		this.bubbleUp();
	}
	remove() {
		let removeTarget = this.items[0];
		if (this.size() === 0) {
			return undefined;
		}
		if (this.size() === 1) {
			return this.items.pop();
		}
		this.items[0] = this.items[this.items.length - 1];
		this.items.pop();
		this.bubbleDown();
		return removeTarget;
	}
}
class MaxHeap extends Heap {
	bubbleUp() {
		let index = this.items.length - 1;
		while (
			this.parent(index) !== undefined &&
			this.parent(index) < this.items[index]
		) {
			this.swap(index, this.parentIndex(index));
			index = this.parentIndex(index);
		}
	}
	bubbleDown() {
		let index = 0;
		while (
			this.leftChild(index) !== undefined &&
			this.leftChild(index) > this.items[index]
		) {
			let largerIndex = this.leftChildIndex(index);
			if (
				this.rightChild(index) !== undefined &&
				this.rightChild(index) > this.items[index]
			) {
				if (this.rightChild(index) > this.leftChild(index)) {
					largerIndex = this.rightChildIndex(index);
				}
			}
			this.swap(index, largerIndex);
			index = largerIndex;
		}
	}
	add(item) {
		this.items[this.items.length] = item;
		this.bubbleUp();
	}
	remove() {
		let removeTarget = this.items[0];
		if (this.size() === 0) {
			return undefined;
		}
		if (this.size() === 1) {
			return this.items.pop();
		}
		this.items[0] = this.items[this.items.length - 1];
		this.items.pop();
		this.bubbleDown();
		return removeTarget;
	}
}
function solution(inputArguments) {
	const [N, ...rest] = inputArguments;
	const maxHeap = new MaxHeap();
	const minHeap = new MinHeap();
	const result = [];
	rest.forEach((e, index) => {
		if (index % 2 === 0) {
			maxHeap.add(e);
		} else {
			minHeap.add(e);
		}
		while (
			maxHeap.peek() !== undefined &&
			minHeap.peek() !== undefined &&
			maxHeap.peek() > minHeap.peek()
		) {
			const maxSwapTarget = maxHeap.remove();
			const minSwapTarget = minHeap.remove();
			maxHeap.add(minSwapTarget);
			minHeap.add(maxSwapTarget);
		}
		result.push(maxHeap.peek());
	});
	return result.join("\n");
}
console.log(solution(input));

doju 1년 전 1

bubbleDown()의 구현에 문제가 있어 보입니다. while문의 조건이 왼쪽 자식만 검사하고 있기 때문에, 오른쪽 자식이 자신보다 더 작더라도 왼쪽 자식이 자신의 값 이상이면 반복문이 종료되어 버립니다(MinHeap 기준).

rhrudwnszoq 1년 전 0

고맙습니다 덕분에 잘 해결했습니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC