[백준] 10819번 : 차이를 최대로 - 자바(JAVA)

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

10819번: 차이를 최대로

문제 해석

N개의 정수로 이루어진 배열 A가 주어지면 정수의 순서를 적절히 바꿔 아래의 식의 최댓값을 구해야 한다.

| A[0] - A[1] | + | A[1] - A[2] | + ....... + | A[N-2] - A[N-1] |

---

입력

첫째 줄에는 N이 주어진다.

둘째 줄에는 배열 A에 들어가 있는 정수들이 주어진다.

 

제약조건

3 <= N <= 8

-100 <= 배열의 정수들 <= 100

---

출력

배열의 순서를 적절히 바꾸어 최댓값을 출력한다.

---

문제 풀이 전 설계

첫째 줄에 N을 입력받고 2번째 줄에 배열의 정수를 입력받는다.

이후에 공백을 기준으로 배열의 정수들을 나누어 저장한다.

 

최댓값을 구하는 방법 예상

1. 모든 숫자 조합을 다 구성하여 값을 구해본다 (비효율적이라 싫음)

 

2. 절댓값들이 모두 더해지기 때문에 숫자를 정렬하고 반으로 나누어 홀수 인덱스에는 큰 값들을 짝수 인덱스에는 작은 값들을 넣는다.

 

B배열에는 0번 인덱스부터 제일 작은 값부터 중간값까지 커지면서 정렬되어있습니다.

C배열에는 0번 인덱스부터  제일 큰 값부터 중간값까지 작아지면서 정렬되어 있습니다.

 

예시

정렬된 값 1 4 8 10 15 20

B배열 1 4 8

C배열 20 15 10

조합된 배열 1 20 4 15 8 10 = 55

20 1 15 4 10 8 = 50

 

위의 방법은 제일 작은 값이나 제일 큰 값이 좌측 구석에 박혀버림으로써 1번밖에 연산이 일어나지 않음으로써 손해가 발생합니다. 제일 작은 값이나 큰 값은 연산이 2번 일어나야지 무조건 좋습니다.

 

3. 위의 방법과 유사하게 숫자를 정렬하고 반으로 나누어 인덱스에 나누어 저장한다. 하지만 제일 큰 값이나 작은 값이 연산이 2번 일어나도록 조합을 조금 달리해봅니다.

 

B배열에는 0번 인덱스부터 제일 작은 값부터 중간값까지 커지면서 정렬되어있습니다.

C배열에는 0번 인덱스부터  제일 큰 값부터 중간값까지 작아지면서 정렬되어 있습니다.

 

B배열의 큰 값부터 작은 값까지를 A배열 0,2,4...로 배치하고

C배열의 큰 값부터 작은 값까지를 A배열 1,3,5...로 배치합니다.

 

예시

정렬된 값 1 4 8 10 15 20

B배열 1 4 8

C배열 20 15 10

조합된 배열 8 20 4 15 1 10 = 62

 

위의 방법은 제일 큰 값이나 작은 값에서 연산이 2번 발생합니다.

또한 중간값(8, 10)이 좌측 끝, 우측 끝으로 이동하여 연산에서 가장 영향력이 약해집니다.

 

만약에 배열에 음수가 존재할 때도 생각해보겠습니다

정렬된 값 -20 -10 10 20

B배열 -20 -10

C배열 10 20

조합된 배열 -10 20 -20 10 = 100 (잘 동작하는 듯 보입니다)

 

위에서는 배열의 크기가 짝수인데 홀수일 때도 생각해보겠습니다 + 음수 포함

정렬된 값 -20 7 10 20 35

 

Case 1

B배열 -20 7

C배열 10 20 35

조합된 배열 7 35 -20 20 10  (잘 동작하는 것 같습니다)

 

Case2

B배열 -20 7 10

C배열 20 35

조합된 배열 10 20 7 35 -20 (-20 가장 작은 값이 우측으로 가버리면서 연산에 손실이 발생할 것 같습니다)

 

 

어느 정도 생각정리를 하였으니 실제로 개발에 들어가 보겠습니다.

3번 시도해보고 안된다면 완전 탐색인 1번 시도 예정

 

 

---

풀이하면서 고민해본 점

입력은 어떻게 받는 것이 효율적인가( Scanner vs BufferedReader)

https://junuuu.tistory.com/7?category=968252 

[Java] Scanner 와 BufferedReader의 차이점

출력은 어떻게 하는 것이 효율적인가 ( System.out.println vs BufferedWriter) (String vs StringBuilder)

https://blog.naver.com/scyawer/222072629287

자바)System.out.println vs. BufferedReader

 

위의 방법으로 시도해보았을 때 95% 에서 틀렸습니다가 나왔습니다.

반례 케이스를 찾다 보니 -1 0 0 같은 경우의 배열이 들어오면

최댓값을 0 -1 0으로 조합했을 때 2지만 위의 방법은 -1 0 0으로 조합하여 1이 나오는 경우가 발생했습니다.

따라서 배열의 길이가 3이고 0이 2개일 때를 카운트하여 특별 케이스로 처리하였습니다.

하지만 이 경우에도 95%에서 틀렸습니다가 나왔습니다.

 

또한 반례 중 -4 -3 -1 -1 0  배열이 존재합니다.

위의 방법으로 조합하게 되면 -3 0 -4 -1 -1으로 값이 10이 나오지만

-1 -4 0 -3 -1의 경우 값이 12가 나옵니다.

 

이처럼 홀수일 때  -3, -1을 양끝에 배치할 것인가 -1, -1을 양끝에 배치할 것인가에 따라 결과가 달라집니다.

코드 또한 복잡해질 것 같고 또 다른 반례가 나타날 것 같아 완전 탐색으로 계획을 변경했습니다ㅠㅠ 

 

완전 탐색의 핵심 로직만 살펴보겠습니다

static void perm(int depth) {
		if( depth == N) {
			sum();
			return ;
		}
		
		for(int i = depth; i< N; i++) {
			swap(i, depth);
			perm(depth + 1);
			swap(i, depth);
		}
		
	}

perm은 재귀함수입니다.

swap() 메서드는 인자의 인덱스를 기준으로 순서를 교체합니다.

depth는 0부터 시작하는데 {1, 2, 3} 배열의 예시를 들어보겠습니다.

 

depth = 0 일 때

반복문은 0부터 2까지 반복합니다.

 

i=0 일 때

swap(0, 0)

//현재 배열 상태 1, 2, 3

perm(1)

swap(0, 0)

//배열을 다시 되돌림

 

i=1 일 때

swap(1, 0)

//현재 배열 상태 2, 1, 3

perm(1)

swap(1, 0)

 

i=2 일 때

swap(2, 0)

//현재 배열 상태 3, 2, 1

perm(1)

swap(2, 0)

 

이를 통해 depth 0 은 첫 번째 자리를 1, 2, 3으로 고정하며 perm(depth+1)을 호출하여 perm(2)를 호출합니다.

 

여기까지 봤을 때는 아직 뭔지 감이 잘 오지 않으니

i=0 일 때 호출한 perm(1)으로 더 들어가 보겠습니다.

 

depth = 1 일 때

반복문은 1부터 2까지 반복합니다.

 

i=1 일 때

swap(1, 1)

//현재 배열 상태 1, 2, 3

perm(2)

swap(1, 1)

 

i=2 일 때

swap(2, 1)

//현재 배열 상태 1, 3, 2

perm(2)

swap(2, 1)

 

이를 통해 depth 1은 두 번째 자리를 2, 3으로 고정하고 perm(depth+1)을 호출하여 perm(3)을 호출합니다.

 

perm 3이 경우에는 depth = 3 이므로 depth = N이 성립하여 sum() 메서드가 호출되며 return 됩니다.

이를 통해 하나의 순열이 만들어지고 계산하는 과정이 이루어집니다.

 

이를 반복하게 된다면 모든 경우의 수를 탐색하는 순열이 만들어지게 됩니다.

 

---

어려웠던 점

순열을 구성하는 코드에 익숙하지 않았다.

---

삽질한 코드

package algorithm6;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

/*
 * BOJ : 10819번 차이를 최대로
 * N개의 정수로 이루어진 배열 A의 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램
 * | A[0] - A[1] | + | A[1] - A[2] |  + .... + | A[N-2] - A[N-1] |
 */

public class MaxGap {
	public static void main(String[] args) throws NumberFormatException, IOException {
		ArrayList<Integer> arrayListA = new ArrayList<Integer>();
		ArrayList<Integer> spcialList = new ArrayList<Integer>();
		ArrayList<Integer> combinatedArray = new ArrayList<Integer>();
        
		int generalResult = 0;
		arrayListA = makeArray();
		spcialList = (ArrayList<Integer>) arrayListA.clone();
		combinatedArray = combiningArray(arrayListA);
		generalResult = calculateArray(combinatedArray);

		int specialResult = 0;		
		specialResult = checkSpecialCase(spcialList);
		printResult(generalResult, specialResult);

	}

	static ArrayList<Integer> makeArray() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String str = br.readLine();
		String[] strArray = str.split(" ");
		ArrayList<Integer> arrayListA = new ArrayList<Integer>();

		for (String strElement : strArray) {
			arrayListA.add(Integer.parseInt(strElement));
		}

		return arrayListA;
	}

	static ArrayList<Integer> combiningArray(ArrayList<Integer> arrayListA) {
		// A배열 : 정렬된 배열
		// B배열 : A[0] ~ A[middle-1]
		// C배열 : A[middle] ~ A[length-1]
		// conbinatedArray : A[middle-1] A[length-1] A[middle-2] A[length-2] .......
		// A[0] A[middle]
		Collections.sort(arrayListA);
		int length = arrayListA.size();
		int middle = length / 2;

		ArrayList<Integer> combinatedArray = new ArrayList<Integer>();

		if (isEven(length)) {
			for (int i = 0; i < length; i++) {
				if (isEven(i)) {
					combinatedArray.add(arrayListA.get(middle - 1 - (i / 2)));
				} else {
					combinatedArray.add(arrayListA.get(length - 1 - (i / 2)));
				}
			}
		} else {
			for (int i = 0; i < length; i++) {
				if (isEven(i)) {
					// B배열을 먼저 하고싶은데 length가 홀수인경우에는 B배열 이 C배열보다 길이가 1이 작음
					// 하지만 index기준으로 나누어버리게 되면 B배열 index가 더 사용되는일이 발생함
					// 예를 들자면 length=5 ,A배열 = {1,3,5,7,9}라면
					// for문은 0~4까지 반복하고 여기에 짝수는 0,2,4 홀수는 1,3임
					// 반면에 B배열 = {1,3} , C배열 = {5, 7, 9}
					// index가 매칭되지 않음 그래서 index = 4일 때 outOfIndex 에러가 발생하게됨
					// middle = 2 이며 middle - 1 - (i / 2) = 2 -1 - (4/2) = -1
					// 따라서 만약 outOfIndex가 발생하게 된다면 try-catch를 사용하여 C배열이 이용되도록함
					try {
						combinatedArray.add(arrayListA.get(middle - 1 - (i / 2)));
					} catch (Exception e) {
						// TODO: handle exception
						combinatedArray.add(arrayListA.get(length - 1 - (i / 2)));
					}

				} else {
					// 1 3
					combinatedArray.add(arrayListA.get(length - 1 - (i / 2)));
				}				
			}
		}
		System.out.println(combinatedArray);
		return combinatedArray;
	}

	static boolean isEven(int num) {
		if (num % 2 == 0) {
			return true;
		} else {
			return false;
		}
	}

	static int calculateArray(ArrayList<Integer> combinatedArray) {
		int sum = 0;
		for (int i = 0; i < combinatedArray.size() - 1; i++) {
			sum += Math.abs(combinatedArray.get(i) - combinatedArray.get(i + 1));
		}
		return sum;
	}

	static int checkSpecialCase(ArrayList<Integer> arrayListA) {
		int result = 0;
		int length = arrayListA.size();
		// -1 0 0 0 과 같은 일반적인 케이스는 조합을 하면 0 -1 0 0 으로 되어 값이 2로 최대값으로 나오지만
		// -1 0 0 과 같은 홀수에 사이즈가3인 특별한 케이스는 조합하면 -1 0 0이 되어 1이 출력됨 사실은 0 -1 0 으로 조합하여 2가 나와야함
		
		if(length == 3) {
			int count = 0;
			int temp = 0;
			for(int i =0; i<length;i++ ) {
				if(arrayListA.get(i).equals(0)) {
					count++;
				}
				else {
					temp = arrayListA.get(i);
				}
			}
			if(count==2) {
				result = temp > 0 ? temp*2 : (-temp) * 2 ; 
			}
		}
		return result;
	}

	static void printResult(int generalResult, int spcialResult) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		if (generalResult > spcialResult) {
			bw.write(generalResult + "\n");
		} else {
			bw.write(spcialResult + "\n");
		}
		bw.flush();
		bw.close();
	}
}

 

완전 탐색 코드

package algorithm6;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/*
 * BOJ : 10819번 차이를 최대로
 * N개의 정수로 이루어진 배열 A의 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램
 * | A[0] - A[1] | + | A[1] - A[2] |  + .... + | A[N-2] - A[N-1] |
 */

public class MaxGap {
	
	static int arr[];
	static int N;
	static int max;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		makeArray();
		perm(0);
		printResult(max);
	}

	static void makeArray() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String str = br.readLine();
		String[] strArray = str.split(" ");
		arr = new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(strArray[i]);
		}		
	}
		
	static void perm(int depth) {
		if( depth == N) {
			sum();
			return ;
		}
		
		for(int i = depth; i< N; i++) {
			swap(i, depth);
			perm(depth + 1);
			swap(i, depth);
		}
		
	}
	
	static void sum() {
		int sum = 0;
		for(int i=0; i<N-1; i++) {
			sum += Math.abs(arr[i] - arr[i+1]);
		}
		if (sum > max) {
			max = sum;
		}
	}
	
	static void swap(int num1, int num2) {
		int temp = arr[num2];
		arr[num2] = arr[num1];
		arr[num1] = temp;
	}
	
	static void printResult(int result) throws IOException {
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));		
		bw.write(result + "\n");						
		bw.flush();
		bw.close();
	}
}