글 읽기 - 시간초과를 해결할 수 있는 방법이 있을까요?

kmji95 4년 전 0

반례들은 다 맞는 것 같은데 시간초과가 납니다

시간을 줄일 수 있는 방법이 있을까요? 혹시 코드에 문제가 있다면 반례들도 함께 알려주시면 감사하겠습니다ㅠㅠ

import java.util.*;
import java.math.*;

public class Main {
	public static void main(String arg[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int value;
		Permutation p = new Permutation(n);
		for (int i = 0; i < n; i++) {
			value = sc.nextInt();
			p.makeArray(i, value);
		}
		p.sortArray();
		do {
			p.maxValue();
		}while(p.next_permutation());
		p.printArray();
	}
}

class Permutation {
	int[] array;
	int n;
	int max=0;
	int value=0;
	Permutation(int n) {
		this.n = n;
		array = new int[n];
	}

	public void makeArray(int i, int value) {
		array[i] = value;
	}

	public void sortArray() {
		Arrays.sort(array);
	}

	public boolean next_permutation() {
		int a = 0;
		boolean flag = false;
		int MIN=100;
		for (int i = n - 1; i > 0; i--) {
			if (array[i - 1] < array[i]) {
				a = i - 1;
				flag = true;
				break;
			}
		}
		if (flag == false)
			return flag;

		int b = 0;
		for (int j = a + 1; j < n; j++) {
			if (array[a] < array[j] && MIN > array[j]) {
				MIN = array[j];
				b = j;
			}
		}
		
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;

		Arrays.sort(array, a+1, n);
		return flag;
	}

	public void maxValue() {
		for(int i=0; i<n-1; i++) {
			value=value+Math.abs(array[i]-array[i+1]);
		}
		if(max<value) max=value;
		value=0;
	}
	
	public void printArray() {
		System.out.print(max);
	}
}

seunghwanmun 4년 전 0

저도 Java로 구현 했는데.. 동일하게 시간초과 발생 했습니다.

아무리 봐도 다른 데는 별로 고칠 게 없어 보여요.

직접 구현한 next_permutation() 함수가 C++ STL보다 많이 느리지 않을까 생각 해 봅니다.

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

문제

문제

출처

ICPC

시간초과를 해결할 수 있는 방법이 있을까요?

kmji95 4년 전 0

seunghwanmun 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말