[백준 -10819번] 차이를 최대로 - JAVA 정리 및 해설

안녕하세요. 주인장입니다. 오늘은 "차이를 최대로"라는 문제를 풀어볼건데요. 일단 제 생각의 흐름대로 (즉, 삽질 한대로 포스팅을 해보려고 합니다. )

전 이 차이를 최대로 문제가 최대수 - 최소수를 빼면 된다고 생각했습니다. 그러면 max값 구하기에 수월하다고 생각했는데요.

그래서 일단 수를 받은뒤에 정렬을 해서 최소와 최대를 정렬을 하고 

새로운 배열에 제일 최대수 제일 최소수  그다음 최대수 그다음  최소수.... 방식을 취하면 된다고 생각했습니다.

근데 딱히 좋은 방법은 방법은 아니였죠. 이러면 이 최대 합이 56이 나오게 됩니다. 

왜냐하면 이방식은 뭔지는 모르겠지만 (즉, n개수가 많아져서 정확하게 뭐가 뭔지 파악하긴 어렵지만.) 62가 나오는 경우가 아니게 되므로, 이방식으로 풀면 안되는 것이죠.

여기 이게 그 삽질한 코드입니다. (이걸로 하면 답 안나옵니다.)

package codeBaekJoon;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class no10819_MaxSubstract { 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int num[] = new int [n];
		int sum[] = new int [n];
		String number = br.readLine();
		StringTokenizer st = new StringTokenizer(number, " ");
		for(int i =0; i<n; i++){
			num[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(num);
		
		if(n%2==0){ //짝수인 경우 // 6일때 0 1 2 3 4 5 중에서 5 4 3 는 0 2 4에 0 1 2은 1 3 5에 들어가야
			int j=0;
			for(int i=n-1; i>=n/2; i--){
				sum[j] = num[i];
				j+=2;
			}
			int k =1;
			for(int i=0; i<n/2; i++){ // 0 1 2 
				sum[k] = num[i];
				k+=2;
			}
		}
		if(n%2==1){ // 홀수인 경우 // 5일때 0 1 2 3 4  4 3 2은  0 2 4 자리 0 1은 1 3자리에 들어가
			int j=0;
			for(int i=n-1; i>=n/2; i--){
				sum[j] = num[i];
				j+=2;
			}
			int k =1;
			for(int i=0; i<n/2; i++){
				sum[k] = num[i];
				k+=2;
			}
		}
		int total = 0;
		for(int i=2; i<n; i++){
			total += Math.abs(sum[i-2]-sum[i-1]);
		}
		System.out.println(total);
		
		
	}
}
  

그럼 이걸 어떤 방식으로 풀었을때 잘풀었다고 소문이날까 고민을 했는데... 여타 블로그에서 가장 유용하게 쓰는 순열을 이용하라고 하더라구요.

즉, 순열을 이용하는 것은 모든 경우를 다 직접 해보는 것으로 문제를 풀어보는 방식입니다.  지금 이 문제의 경우 조건 자체가 

"첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다." 

이므로,  아주 많이 해본다한들 8! = 40320번정도 하게 된단말이죠? 근데 이걸 직접 손으로 하기에는 많은 양이지만, 컴퓨터가 하기에는 정말 쉬운 양이므로, (컴퓨터는 10억번정도의 연산을 1초에 한다고 가정해도 문제풀때 상당히 유용합니다.)

직접 문제를 다 집어넣어서 푸는 방식으로 해도 됩니다. 근데 이렇게 푸는 방식을 조금 어렵게 말하면 이런식으로도 부를수 있습니다

"Brutal Force" 라고 컴퓨터는 충분히 할 수 있는 정도의 양이지만, 손으로 하기에는 좀 많은 경우를 뜻합니다.

이러면, 순열을 이용하는 방식으로 그럼 문제를 풀어보도록 하겠습니다.

순열 역시 아주 많이 사용되는 알고리즘으로 따로 순열만 모아서 나중에 포스팅하도록 하겠습니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main { // 순열구하기
	static int max =0; 
	public static void perm(int[] a, int depth, int n){
		if(depth==n){
			sum(a, n);
			return;
		}
		for(int i=depth; i<n; i++){
			swap(a, i, depth);
			perm(a, depth+1, n);
			swap(a, i, depth);
		}
	}
	
	
	static void swap(int[] a, int depth, int n) {
		int temp = a[depth];
		a[depth] = a[n]; 
		a[n] = temp;
		
	}


	static void sum(int[] a, int k) {
		int sum =0;
		for (int i = 2; i <= k; i++) { 
			sum += Math.abs(a[i-2]-a[i-1]);
		}
		if(max<sum){
			max = sum;
		}

	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int num[] = new int [n];
		String number = br.readLine();
		StringTokenizer st = new StringTokenizer(number, " ");
		for(int i =0; i<n; i++){
			num[i] = Integer.parseInt(st.nextToken());
		}
		perm(num, 0, n);
		System.out.println(max);

		
		
		
	}
}

순열을 구하는 문제는 그냥 perm()함수와 swap()함수 이 두개를 동시에 가져가면 좋습니다. 이 알고리즘은 자리를 perm는 말그대로 순열을 만드는 문제고, swap은 그 배열안의 모든 원소들을 자리 이동하는 함수이므로, 그것을 잘 섞어서 연결해주면 됩니다.

이상으로 포스팅을 끝내겠습니다. 

https://www.acmicpc.net/problem/10819

차이를 최대로 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	6678	3993	3111	60.857%