백준 10819. 차이를 최대로

🅰 백준 10819. 차이를 최대로

10819번: 차이를 최대로

✏️ 문제 풀이

• 백트래킹을 사용하지 않고 순열을 이용하여 모든 경우의 수에 따라 값을 구해준 다음에
• Math.max 를 이용하여 차이가 최대값인 값을 지정해주었다.

✏️ 소스코드

package bruteforce;
import java.util.*;
import java.io.*;
public class Main_실버2_10819_손은성 {
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int input[] = new int[N];
		int max = Integer.MIN_VALUE;
		int ans = 0;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			input[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(input);
		
		do {
			// ans 계산
			for (int i = 0; i < N-1; i++) {
				ans += Math.abs(input[i] - input[i+1]);
			}
			max = Math.max(max, ans);
			ans = 0;
		}while(np(input));
		
		System.out.println(max);
	}

	// next-permutation
	private static boolean np(int[] input) {
		int N = input.length-1;
		
		int i = N;
		while(i>0 && input[i-1]>=input[i]) --i;
		if(i == 0)
			return false;
		
		int j = N;
		while(input[i-1] >= input[j]) --j;
		swap(input, i-1, j);
		
		int k = N;
		while(i<k) swap(input, i++, k--);
		
		return true;
	}

	private static void swap(int[] input, int i, int j) {
		int temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}
}

 

✅ 후기

•