글 읽기 - 자바 힙 소트 구현 시 시간초과 질문

chickenman 3년 전 1

완벽하게 nlogn 로직이 아닌것 같아 질문드립니다. 어떤 부분이 잘못 되었을까요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  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());
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = Integer.parseInt(br.readLine());
    }
      
    heapSort(a);
    for (int i = 0; i < n; i++) {
      sb.append(a[i] + " ");
    }
    System.out.println(sb);
  }

  static void heapSort(int[] arr) {
    maxHeapify(arr, arr.length);
    for (int i = arr.length - 1; i > 0; i--) {
      swap(arr, 0, i);
      maxHeapify(arr, i);
    }
  }

  static void maxHeapify(int[] a, int idx) {
    for (int i = 1; i < idx; i++) {
      int child = i;
      while (child > 0) {
        int parent = (child-1) /2;
        if (a[child] > a[parent]) {
          swap(a, child, parent);
        }
        child = parent;
      }
    }
  }
}

djm03178 3년 전 1

maxHeapify 함수는 idx로부터 밑으로 내려가기만 하고 끝나야 합니다. 1부터 idx까지를 다 보는 것이 아닙니다.

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

문제

문제

출처

ICPC

자바 힙 소트 구현 시 시간초과 질문

chickenman 3년 전 1

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말