글 읽기 - 시간초과ㅠㅠ

shkim950921 5년 전 0

자꾸 시간초과뜨는데 어딜 어떻게 해야하나요ㅠㅠ

import java.util.ArrayList;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
String rawInput;
int N;
int K;

int middle;

List<Integer> listArray = new ArrayList<Integer>();

listArray.add(0);
Scanner scan = new Scanner(System.in);
rawInput = scan.nextLine();
String[] splitInput = rawInput.split(" ");

N = Integer.parseInt(splitInput[0]);
K = Integer.parseInt(splitInput[1]);

middle = (K + 1) / 2;

long[] array = new long[K];
ArrayList<Integer> copyArray = new ArrayList<Integer>();
ArrayList<Integer> arrayList = new ArrayList<Integer>();
int flag = 0;
long Sum = 0;

for (int i = 0; i < N; i++) {
int scanInteger = scan.nextInt();
if (flag == 1) {
arrayList.add(scanInteger);
arrayList.remove(0);
} else {
arrayList.add(scanInteger);
array[i] = scanInteger;
}
if (i >= K - 1) {

copyArray.removeAll(copyArray);
copyArray.addAll(arrayList);

long sum = sort(copyArray, 0, K - 1, middle);
Sum += sum;

flag = 1;
}
}
System.out.println(Sum);
}

private static long sort(ArrayList<Integer> castArray, int start, int end, int middle) {
// TODO Auto-generated method stub
mergeSort(castArray, start, end, middle);
return castArray.get(middle - 1);
}

private static void mergeSort(ArrayList<Integer> castArray, int start, int end, int middle) {
int mid = (start + end) / 2;
if (end - start < 1)
return;
else {
mergeSort(castArray, start, mid, middle);
mergeSort(castArray, mid + 1, end, middle);
merge(castArray, start, end,mid);}

}

private static void merge(ArrayList<Integer> castArray, int start, int end,int mid) {
// TODO Auto-generated method stub
int ftIndex = start;
int sndIndex = mid+1;


ArrayList<Integer> mergeList = new ArrayList<Integer>();
while (ftIndex <= sndIndex && sndIndex <= end) {
if (castArray.get(ftIndex) > castArray.get(sndIndex)) {
mergeList.add(castArray.get(sndIndex));
sndIndex++;
} else {
mergeList.add(castArray.get(ftIndex));
ftIndex++;
}
}
if(sndIndex<end){
while (sndIndex <= end) {
mergeList.add(castArray.get(sndIndex));
sndIndex++;
}
}
else if(ftIndex<sndIndex){
while (ftIndex < sndIndex) {
mergeList.add(castArray.get(ftIndex));
ftIndex++;
}
}

for (int i = start; i <= end; i++) {
castArray.set(i, mergeList.get(i - start));
}

}


}

djm03178 5년 전 0

단순히 매번 정렬하는 식으로 해결할 수 있는 문제가 아닙니다. 다른 질문들을 참고하세요.

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

문제

문제

출처

ICPC

시간초과ㅠㅠ

shkim950921 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말