[백준] 10819번 : 차이를 최대로 - 자바(JAVA)
https://www.acmicpc.net/problem/10819
10819번: 차이를 최대로
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
www.acmicpc.net
문제 해석
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의 차이점
두 클래스는 모두 자바에서 입력을 받는 데 사용이 됩니다. BufferedReader 우선 BufferedReader는 InputStreamReader에 버퍼링 기능이 추가된 Class입니다. 사용자가 요청할 때마다 데이터를 읽어 오는 것이 아
junuuu.tistory.com
출력은 어떻게 하는 것이 효율적인가 ( System.out.println vs BufferedWriter) (String vs StringBuilder)
https://blog.naver.com/scyawer/222072629287
자바)System.out.println vs. BufferedReader
하드디스크는 원래 속도가 엄청 느립니다. 하드뿐만 아니라 키보드나 모니터와 같은 외부 장치와의 데이터 ...
blog.naver.com
위의 방법으로 시도해보았을 때 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();
}
}