글 읽기 - 시간초과 해결좀 해주시면 감사하겠습니다ㅜㅜ

wldnd923 6년 전 1

힙정렬이랑 다른정렬을 혼합해서 정렬해야하는건지..

아니면 제가 힙정렬을 잘못짜서 시간초과가 나는건지 도무지 모르겠습니다..

해결해주시면 너무 감사드리겠습니다 ..ㅜㅜ

-------------------------------------------------------------------------------------------------------------

O(n^2) 시간복잡도를 가진다는 부분을 수정해서 돌려봤는데 틀렸다고 나옵니다..ㅜ

수정좀 해주시면 감사하겠습니다..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] unsorted = new int[N];
		int[] iValue = new int[N];
		
		for (int i = 0; i < N; i++) {
			unsorted[i] = Integer.parseInt(br.readLine());
		}

		// 최대힙 만들기 루트로부터 중간지점 되는 노드부터 다시 루트까지 최대힙정렬
		maxHeap(unsorted);

		// 최대힙정렬된 트리에서 루트부터 하나씩 빼서 새배열의 마지막 공간부터 앞으로 내림차순으로 할당해주기.
		deletionHeap(unsorted, iValue);

		for (int i = 0; i < iValue.length; i++) 
			System.out.print(iValue[i] + "\n");
		 bw.flush();
		 bw.close();
	}

	// 최대힙 만들기.
	public static void maxHeap(int[] unsorted) {
		int start = (unsorted.length / 2) - 1; // 전체노드개수의 반인 노드부터 시작해 루트까지 진행할
												// 시작점이다.
		for (int i = start; i >= 0; i--)
			makeHeap(unsorted, i);
	}

	public static void deletionHeap(int[] oldArray, int[] newArray) {
		int numberOfNode = oldArray.length; // 10
		// 최대힙을 다 빼야되므로 최대힙의 노드개수만큼 돌려준다.
		for (int i = 0; i < oldArray.length; i++) {
			// 루트노드의 노드를 새 배열에 할당해준뒤 제거하고 맨 마지막 노드를 루트로 옮긴다.
			newArray[numberOfNode - 1] = oldArray[0];
			oldArray[0] = oldArray[numberOfNode - 1];
			oldArray[numberOfNode - 1] = 0;
			numberOfNode--;
			makeHeap(oldArray, 0);
			// 루트는 높이0 루트의 자식은 높이1... 완전이진트리의 가장 끝노드의 높이: h = log2(N+1) N= 노드의
			// 갯수
			// int height = (int) baseLog(numberOfNode + 1, 2);
			// 루트부터 최대힙정렬
			// for (int j = 0; j < height; j++) {
			// makeHeap(oldArray, j);
			// }
		}
	}

	public static void makeHeap(int[] a, int i) {
		int num = a.length - 1;

		int max = i;
		// left_child가 존재할 때
		if ((i * 2) + 1 <= num) {
			// left_child가 부모보다 크면
			if (a[i * 2 + 1] > a[max]) {
				max = (i * 2) + 1;
			}
		} else {
			return;
		}
		// right_child가 존재할 때
		if ((i * 2) + 2 <= num) {
			// right_child가 부모보다 크면
			if (a[i * 2 + 2] > a[max]) {
				max = (i * 2) + 2;
			}
		}
		// 부모가 max가 아니면 값이 큰 자식과 부모와 교환
		if (max != i) {
			swap(a, i, max);
			makeHeap(a, max);
		}
	}

	public static double baseLog(double x, double base) {
		return Math.log10(x) / Math.log10(base);
	}

	public static void swap(int[] arr, int Old, int New) {
		int temp = arr[Old];
		arr[Old] = arr[New];
		arr[New] = temp;
	}
}

djm03178 6년 전 1

39~41번째 줄은 O(N^2*lgN)입니다. 자체 루프만으로도 O(N^2)입니다. 처음에 힙을 만드는 과정은 O(NlgN)에 할 수 있습니다.

wldnd923 6년 전 0

감사합니다 수정해보겠씁니다

wldnd923 6년 전 0

자체루프 시간복잡도를 해결해서 돌렸는데 틀렸다고나옵니다.. 어디가 잘못된건지 알려주시면 감사하겠습니다..ㅜ

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

문제

문제

출처

ICPC

시간초과 해결좀 해주시면 감사하겠습니다ㅜㅜ

wldnd923 6년 전 1

djm03178 6년 전 1

wldnd923 6년 전 0

wldnd923 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말