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

chickenman 3년 전 1

완벽하게 O(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());
    }

    mergeSort(a,0, n-1);
    for (int i = 0; i < n; i++) {
      sb.append(a[i] + " ");
    }
    System.out.println(sb);
  }

  static void mergeSort(int[] arr, int start, int end) {
    if (start < end) {
      int mid = (start + end) / 2;
      mergeSort(arr, start, mid);
      mergeSort(arr,mid + 1, end);
      merge(arr, start, mid, end);
    }
  }

  static void merge(int[] arr, int start, int mid, int end) {
    int[] tmp = new int[arr.length];
    for (int i = start; i <= end; i++) {
      tmp[i] = arr[i];
    }
    int part1 = start;
    int part2 = mid+1;
    int index = start; //tmp배열 복사 시작 인덱

    while (part1 <= mid && part2 <= end) {
      if (tmp[part1] <= tmp[part2]) {
        arr[index++] = tmp[part1++];
      } else {
        arr[index++] = tmp[part2++];
      }
    }

    for (int i = 0; i <= mid - part1; i++) {
      arr[index + i] = tmp[part1 + i];
    }
  }
}

djm03178 3년 전 1

tmp 배열을 매번 arr.length만큼 할당하면 메모리 할당량이 총 O(n^2)이 되고, 할당 시간은 할당 크기에 비례하기 때문에 시간 복잡도도 O(n^2)이 됩니다. end - start + 1만큼씩만 할당하거나, 할당을 매번 하지 않고 미리 할당해둔 배열을 재사용해야 합니다.

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

문제

문제

출처

ICPC

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

chickenman 3년 전 1

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말