순열을 활용한 차이 최대값 구하기_BOJ_10819

사실 이 문제를 이해하기 위해서 좀 오래걸렸다.

주어진 배열을 먼저 오름차순으로 정렬한 뒤 다음 순열 공식을 이용해서 이 중 반복문을 거치고 

이를 통해 문제에서 요구하는 최대 차의 값을 구하도록 만드는 것이다.

코드 부터 확인해보자

public static void main(String[] args) {

// TODO Auto-generated method stub

sc = new Scanner(System.in);

int N = sc.nextInt();

int[] A = new int[N];

for (int i = 0; i < N; i++)

A[i] = sc.nextInt(); // 배열 안에 넣기

Arrays.sort(A); // 오름 차순 정리

int max = 0;

do {

int tmp = calculate(A);

max = Math.max(max, tmp);

} while (next_permutation(A));

System.out.println(max);

}

메인 함수 부터 확인해보자.

우선 배열로 입력 받은 것을 오름 차순 정리를 통해서 재배열 해야 한다.

그래야만 다음 순열 공식을 이용하기 편할 뿐더러 횟수도 줄어든다.

차이 계산 함수는 다음과 같다.

// 차이 계산

private static int calculate(int[] a) {

int sum = 0;

for (int i = 1; i < a.length; i++) {

sum += Math.abs(a[i] - a[i - 1]);

}

return sum;

}

여기서 중요한 것은 i의 범위이다.

1부터 배열의 길이 이 전까지로 잡거나 

int i = 1 ; i < (int) a. length - 1 로 정의해야 한다.

이유는 i가 unsigned int일 경우 음수가 되면 unsigned 함수의 범위에서 최대로 이동되기 때문에

무한 루프가 발생할 수 있다.

다음 순열 함수이다.

---

private static boolean next_permutation(int[] A) {

int i = A.length - 1;

while (i > 0 && A[i] <= A[i - 1]) {

i -= 1;

}

if (i <= 0)

return false;

int j = A.length - 1;

while (A[j] <= A[i - 1]) {

j -= 1;

}

int temp = A[i - 1];

A[i - 1] = A[j];

A[j] = temp;

j = A.length - 1;

while (i < j) {

int temp2 = A[i];

A[i] = A[j];

A[j] = temp2;

i += 1;

j -= 1;

/*

System.out.println("i " + A[i] + "   ");

System.out.println("j " + A[j] + "   ");

*/}

for(int k=0;k<A.length;k++) {

System.out.println("K " + A[k] + "   ");

}

return true;

}

---

이는 다음 순열이 A[i-1] >= A[i] && i > 0 인 경우 i를 줄여주면서 i가 다음 조건을 만족하지 않을 때,

i는 최대의 값을 가지게 됩니다.

(조건에 따르면)

A[i-1]과 A[i]를 교체해주고A[j] 값 또한 A[i-1]의 값보다 작거나 같은 수를 뽑아서 A[i-1]과 교체해준다.

이 후에는 j는 다시 배열의 마지막 인덱스에서의 값과 i의 값과 계속 비교하면서 변경해준다.

다음과 같이 진행한다면 최종적으로는 내림차순으로 정리가 될 것입니다.

이렇게 진행하는 와중에 차이가 최대 값을 구해야하므로 

---

do {

int tmp = calculate(A);

max = Math.max(max, tmp);

} while (next_permutation(A));

---

메인 함수에서 다음과 같은 알고리즘을 거치는 것이다.

여기서 계속 작업하면서 최대를 구하고 그 최대값을 출력하는 것이다.

전체 코드 

package 탐색;

import java.util.Arrays;

import java.util.Scanner;

public class 차이를_최대로 {

private static Scanner sc;

public static void main(String[] args) {

// TODO Auto-generated method stub

sc = new Scanner(System.in);

int N = sc.nextInt();

int[] A = new int[N];

for (int i = 0; i < N; i++)

A[i] = sc.nextInt(); // 배열 안에 넣기

Arrays.sort(A); // 오름 차순 정리

int max = 0;

do {

int tmp = calculate(A);

max = Math.max(max, tmp);

} while (next_permutation(A));

System.out.println(max);

}

private static boolean next_permutation(int[] A) {

int i = A.length - 1;

while (i > 0 && A[i] <= A[i - 1]) {

i -= 1;

}

if (i <= 0)

return false;

int j = A.length - 1;

while (A[j] <= A[i - 1]) {

j -= 1;

}

int temp = A[i - 1];

A[i - 1] = A[j];

A[j] = temp;

j = A.length - 1;

while (i < j) {

int temp2 = A[i];

A[i] = A[j];

A[j] = temp2;

i += 1;

j -= 1;

/*

System.out.println("i " + A[i] + "   ");

System.out.println("j " + A[j] + "   ");

*/}

for(int k=0;k<A.length;k++) {

System.out.println("K " + A[k] + "   ");

}

return true;

}

// 차이 계산

private static int calculate(int[] a) {

int sum = 0;

for (int i = 1; i < a.length; i++) {

sum += Math.abs(a[i] - a[i - 1]);

}

return sum;

}

}