글 읽기 - 힙 구현으로 풀었을때 틀린것

bindy1226 3년 전 0

우선순위 큐 말고 힙 구현으로 풀어보려했으나..

7퍼센트 중에 틀렸다고 나옵니다.

인덱스 0인 부분때문에 틀린것 같아서 이것저것 해봤는데도 결과는 잘 나와서 질문 올렸습니다.

도와주시면 감사하겠습니다.

import java.util.*;

public class Main {
	public static class maxHeap{
		private ArrayList<Integer> list;
		
		public maxHeap(){
			list = new ArrayList<>();
			list.add(Integer.MAX_VALUE);
		}
		
		public void insert(int input){
			list.add(input);
			int w = list.size() - 1;
			while(w > 1 && list.get(w/2) < list.get(w)){
				int tmp = list.get(w/2);
				list.set(w/2, list.get(w));
				list.set(w, tmp);
				w /= 2;
			}
		}
		
		public int pop(){
			if(list.size()-1 < 1){
				return 0;
			}
			int toPop = list.get(1);
			list.set(1, list.get(list.size()-1));
			list.remove(list.size()-1);
			
			int w = 1;
			while((w*2) < list.size()){
				int max = list.get(w*2);
				int maxW = w*2;
				if(((w*2 + 1) < list.size()) && max > list.get(w*2 + 1)){
					max = list.get(w*2 + 1);
					maxW = w*2 + 1;
				}
				if(list.get(w) > max){
					break;
				}
				int tmp = list.get(w);
				list.set(w, list.get(maxW));
				list.set(maxW, tmp);
				w = maxW;
			}
			return toPop;
		}
	}
	
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		maxHeap heap = new maxHeap();
		
		
		for(int i=0;i<N;i++){
			int x = sc.nextInt();
			if(x == 0){
				System.out.println(heap.pop());
			}else{
				heap.insert(x);
			}
		}
		
	}
}

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

문제

문제

출처

ICPC

힙 구현으로 풀었을때 틀린것

bindy1226 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말