글 읽기 - 자바 맥스힙 직접 구현 시간초과..

sight 4년 전 0

Priority Queue를 안쓰고 직접 힙 구현을 했는데 계속 시간 초과가 나네요 ㅜㅜ 어느부분을 고쳐야 할까요

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * 문제 출제  : 백준
 * 문제 링크  : https://www.acmicpc.net/problem/11279
 *
 * @author Sight
 * @since  2020/01/30
 * 
 */
class Main {
    
    static Scanner           sc = new Scanner(System.in);
    static List<Integer> result = new LinkedList<>();

    public static void main(String[] args) {
        Main p = new Main();
        p.solution(sc.nextInt());
    }

    void solution(int cnt)
    {
        MaxHeap heap = new MaxHeap(cnt);

        for (int i = 0; i < cnt; i++)
        {
            int param = sc.nextInt();
            if (param == 0) {
                result.add(heap.pop());
            } else {
                heap.add(param);
            }
        }

        System.out.print(
                result.stream()
                        .map(String::valueOf)
                        .collect(Collectors.joining("\n"))
        );
    }
}

class MaxHeap {

    private int[]    heap;
    private int  heapSize;

    public MaxHeap(int size) {
        this.heap     = new int[size+1];
        this.heapSize = 0;
    }

    public void add(int param) {
        heapSize++;
        heap[heapSize] = param;

        for (int i = heapSize; i > 1; i/=2) {
            if(heap[i/2] < heap[i]) {
                swap(i, i/2);
            }
        }
    }

    public int pop() {

        int root = heap[1];
        heap[1] = heap[heapSize];
        heap[heapSize] = 0;

        if (heapSize > 1) {
            heapSize--;
        }

        for (int i = 1; i*2 <= heapSize;) {
            if(heap[i] > heap[i*2] && heap[i] > heap[i*2+1]) {
                break;
            }
            else if(heap[i*2] > heap[i*2+1]) {
                swap(i, i*2);
                i = i*2;
            }
            else if(heap[i*2] < heap[i*2 + 1]) {
                swap(i, i*2 + 1);
                i = i*2 + 1;
            }
        }
        return root;
    }

    private void swap(int a, int b) {
        int temp = heap[a];
        heap[a]  = heap[b];
        heap[b]  = temp;
    }
}