글 읽기 - 어디가 잘못된 건지 모르겠습니다. 반례를 찾을 수 없습니다.

qkrtngus116 1년 전 0

백준 예제는 잘 출력이 되는데 틀렸습니다 라고 뜹니다 ㅠㅠ

반례가 있을까요?

package baekjun.Heap;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main11279 {
	
	static class MaxHeap{
		
		static ArrayList<Integer> heapArray;
		
		MaxHeap(){
			heapArray = new ArrayList<Integer>();
			heapArray.add(null);
		}
		
		public void insert(int data) {
			int inserted_idx, parent_idx;
			
			if(heapArray.size() <= 1) {
				heapArray.add(data);
				return;
			} else {
				heapArray.add(data);
				inserted_idx = heapArray.size() - 1;
				while(this.insertswap(inserted_idx)) {
					parent_idx = inserted_idx / 2;
					Collections.swap(heapArray, inserted_idx, parent_idx);
					inserted_idx = parent_idx;
					if(inserted_idx == 1) {
						return;
					}
				}
			}
		}
		
		public boolean insertswap(Integer inserted_idx) {
			
			int parent_idx = inserted_idx / 2;
			
			if(heapArray.get(parent_idx) < heapArray.get(inserted_idx)) {
				return true;
			} else {
				return false;
			}
		}
		
		public Integer poll() {
			
			Integer polled;
			int rooted_idx = 1;
			int parent_idx;
			
			if(heapArray.size() <= 2) {
				polled = heapArray.remove(rooted_idx);
				return polled;
			} else {
				polled = heapArray.get(rooted_idx);
				heapArray.set(rooted_idx, heapArray.get(heapArray.size() - 1));
				heapArray.remove(heapArray.size()-1);
				
				while(this.pollswap(rooted_idx)) {
					int rooted_left_idx = rooted_idx * 2; 
					int rooted_right_idx = rooted_idx * 2 + 1;
					
					if(rooted_right_idx >= heapArray.size() - 1) {
						Collections.swap(heapArray, rooted_left_idx, rooted_idx);
						rooted_idx = rooted_left_idx;
					} else {
						if(heapArray.get(rooted_left_idx) > heapArray.get(rooted_right_idx)){
							if(heapArray.get(rooted_left_idx) > heapArray.get(rooted_idx)) {
								Collections.swap(heapArray, rooted_left_idx, rooted_idx);
								rooted_idx = rooted_left_idx;
							}
						} else {
							if(heapArray.get(rooted_right_idx) > heapArray.get(rooted_idx)) {
								Collections.swap(heapArray, rooted_right_idx, rooted_idx);
								rooted_idx = rooted_right_idx;
							}
						}
					}
				}
				
				return polled;
			}
		}
		
		public boolean pollswap(int rooted_idx) {
			int rooted_left_idx = rooted_idx * 2; 
			int rooted_right_idx = rooted_idx * 2 + 1;
			if(rooted_left_idx >= heapArray.size()) {
				return false;
			} else if(rooted_right_idx >= heapArray.size()){
				if(heapArray.get(rooted_left_idx) > heapArray.get(rooted_idx)) {
					return true;
				} else {
					return false;
				}
			} else {
				if(heapArray.get(rooted_left_idx) > heapArray.get(rooted_right_idx)) {
					if(heapArray.get(rooted_left_idx) > heapArray.get(rooted_idx)) {
						return true;
					} else {
						return false;
					}
				} else {
					if(heapArray.get(rooted_right_idx) > heapArray.get(rooted_idx)) {
						return true;
					} else {
						return false;
					}
				}
			}
		}
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		MaxHeap heap = new MaxHeap();
		
		for(int i=0; i<N; i++) {
			int a = Integer.parseInt(br.readLine());
			if(a > 0) {
				heap.insert(a);
				//System.out.println(heap.heapArray);
			} else {
				if(heap.heapArray.size() <= 1) {
					sb.append(0);
					sb.append("\n");
					//System.out.println(heap.heapArray);
					//System.out.println(heap.heapArray.size());
				} else {
					sb.append(heap.poll());
					sb.append("\n");
					//System.out.println(heap.heapArray);
					//System.out.println(heap.heapArray.size());
				}
			}
		}
		
		System.out.println(sb);
		//System.out.println(heap.heapArray);
	}
}

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

문제

문제

출처

ICPC

어디가 잘못된 건지 모르겠습니다. 반례를 찾을 수 없습니다.

qkrtngus116 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말