글 읽기 - 병합정렬로 시간초과 도와주세요 ㅠ.ㅠ

wnsals1346 1년 전 0

ㅠㅠ 제생각엔 정석적으로 짠거같은데..

시간을 어떻게 더줄여야 할까요?

package BaekJoonStep.s10;
//https://www.acmicpc.net/problem/2751 - 수 정렬하기 2

import java.io.*;

public class P2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for(int i=0;i<n;i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++) {
            bw.write(arr[i]+"\n");
        }
        bw.close();
        br.close();
    }
    static void mergeSort(int[] arr, int left, int right) {
        if(left<right) {
            int mid = (left+right)/2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);
            merge(arr, left, mid, right);
        }
    }
    static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        int i = left, j = mid+1, k = left;
        while(i<=mid && j<=right) {
            if(arr[i]<=arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while(i<=mid) {
            temp[k++] = arr[i++];
        }
        while(j<=right) {
            temp[k++] = arr[j++];
        }
        for(int l=left;l<=right;l++) {
            arr[l] = temp[l];
        }
    }
}

djm03178 1년 전 1

31번째 줄에서 arr 전체의 크기만큼 새 배열을 만드는 것이 문제입니다. merge 함수는 어떠한 경우에도 자신이 담당하는 범위보다 큰 연산을 해서는 안 됩니다.

wnsals1346 1년 전 0

선생님 도움감사드립니다! 제가 잘못이해했네요. 다시 생각해서 구현하도록 하겠습니다!

wnsals1346 1년 전 0

감사합니다. 배열크기를 필요한 부분으로 조정했더니 시간내에 풀었습니다!!!!

int[] temp = new int[right-left+1]

i = left;
k = 0;
while(i<=right) {
    arr[i++] = temp[k++];
}

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

문제

문제

출처

ICPC

병합정렬로 시간초과 도와주세요 ㅠ.ㅠ

wnsals1346 1년 전 0

djm03178 1년 전 1

wnsals1346 1년 전 0

wnsals1346 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말