[백준 *Java] - 차이를 최대로(10819)

차이를 최대로

10819번: 차이를 최대로

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

---

👇 접근 방식 (내 생각정리)

처음에는 테스트케이스를 가지고, 어떻게 수열을 배치하면? 테스트케이스 출력 값이 나오지? 라는 생각에 계속 그것만 붙잡고 생각했습니다. 그냥 생각에 가장 큰 수와 가장 작은 수를 빼주는 형식으로 겹치는 수가 적은 수든 큰 수든 해서 만들면 되지 않을까? 라는 생각에 계속 규칙? 이라고 해야하나 그런 걸 찾아보려고 했습니다.

결국, 그런 식으로 풀리지가 않아서 스트레스 받고있다가.

생각을 해보니깐 해당 문제는 최대값을 구하면 되는 문제였습니다. 

무슨말이냐,

그냥 전체 배열을 나열하는되, 문제에서 나왔듯이 정수의 순서를 적절히 바꾸기면 하면 된다고 했습니다

그러면 이 문제는 순열문제라고 생각이 됐습니다.

순열 문제이지만, 겹치는 부분을 포함해서 위에서 말한 식을 연산처리만 해주면 된다는 생각에

방문처리 로직에 식을 더하는 로직을 더하면 될 거 같았습니다.

아래는 구현을 해보겠습니다.

아...

이번 문제로 느꼈던 점은 테스트케이스를 너무 의존하지는 말고, 문제를 기반으로 생각하고 풀어도 된다고 생각을 했습니다.제가 생각했던 로직이, 테스트케이스를 보고 난 뒤 맞고 틀리고를 확인하고 문제를 푸는 게 습관이 되어 있어서계속 테스트케이스에서 로직을 확인했던 거 같습니다.

---

아래는 구현한 코드 입니다.

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

public class Main {
    static int N;
    static int[] arr;
    static int[] inputDataArr;
    static boolean[] visited;
    static int MAX = 0;

    static void backTracking(int depth) {

        // base case
        if (depth == N) {
            int sum = 0;
            for (int i = 0; i < N - 1; i++) {
                sum += Math.abs(arr[i] - arr[i+1]);
            }
            MAX = Math.max(MAX, sum);
            return;
        }

        // recur
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = inputDataArr[i];
                backTracking(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        inputDataArr = new int[N];
        for (int i = 0; i < N; i++) {
            inputDataArr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(inputDataArr);

        visited = new boolean[N];
        backTracking(0);

        System.out.println(MAX);
    }
}