[백준] 10819 : 차이를 최대로 (JAVA)

문제

BOJ 10819 : 차이를 최대로 - https://www.acmicpc.net/problem/10819

풀이

처음에는 정렬을 해야하나 생각했는데 그냥 모든 경우의 수 구해서 최댓값 구하면 되는 문제!

경우의 수 구하는 로직은 DFS 사용했고, 주어진 식의 결과값 구하는 로직 메서드로 분리해서 구현함.

코드

코드1 : 경우의 수 저장하는 자료구조 int[] 사용

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

public class Main {
    static int[] nums;
    static boolean[] visited;
    static int[] selected;
    static int n;
    static int result = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        nums = new int[n];
        visited = new boolean[n];
        selected = new int[n];

        for(int i=0; i<n; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        dfs(0);

        System.out.println(result);
    }

    public static void dfs(int count) {
        if(count==n){
            result = Math.max(getResult(), result);
            return;
        }
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                selected[count] = nums[i];
                dfs(count+1);
                visited[i] = false;
            }
        }
    }

    public static int getResult(){
        int sum=0;
        for(int i=0; i<n-1; i++){
            sum += Math.abs(selected[i]-selected[i+1]);
        }
        return sum;
    }
}

코드2 : 경우의 수 저장하는 자료구조 ArrayList 사용

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

public class Main {
    static int[] nums;
    static boolean[] visited;
    static int n;
    static int result = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        nums = new int[n];
        visited = new boolean[n];

        for(int i=0; i<n; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        ArrayList<Integer> arr = new ArrayList<>();
        dfs(arr, 0);

        System.out.println(result);
    }

    public static void dfs(ArrayList<Integer> arr, int count) {
        if(count==n){
            result = Math.max(getResult(arr), result);
            return;
        }
        for(int i=0; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                arr.add(nums[i]);
                dfs(arr, count+1);
//                arr.remove(arr.get(arr.size()-1));
//                이렇게 하면 마지막 수와 마지막이 아닌 수 중에 같은 수가 있을 경우 index가 더 작은 객체가 remove된다.
                arr.remove(arr.size()-1);
                visited[i] = false;
            }
        }
    }

    public static int getResult(ArrayList<Integer> arr){
        int sum=0;
        for(int i=0; i<n-1; i++){
            sum += Math.abs(arr.get(i)-arr.get(i+1));
        }
        return sum;
    }
}

정리

✔ 알고리즘 분류 - 브루트포스 알고리즘, 백트래킹
✔ 난이도 - ⚪ Silver 2 

🤦‍♀️ 오늘의 삽질리스트

• ArrayList의 remove()에 대해 잘 알아둘 것. 여기에서 헷갈려놓고 왜 안되지?만 100번함.
  
  처음에 마지막 요소를 삭제하기 위해 arr.remove(arr.get(arr.size()-1)); 라고 썼는데, 이 경우 remove(Object o)로 적용되기 때문에, 마지막 값과 같은 값이 리스트 내에 있을 경우 마지막 요소가 아닌 제일 앞쪽에 위치한 요소가 삭제된다.
  마지막 요소를 삭제하려면 arr.remove(arr.size()-1); 이렇게 쓰자! 이 경우 remove(int index)로 적용됨

• 그리고 문제 제대로 안읽고 식에 절댓값 못봐서 한참 헤맸다. 아휴 증말,,,

참고 사이트

딱히 없음