10819번 - 차이를 최대로

2024-03-19

#JAVA#백준

문제 링크

문제 풀이 시간 : 30분

문제 요약

•
N개의 정수가 주어진다.

•
정수의 순서를 바꿔서 아래 식의 최댓값을 구하라

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

문제 풀이

이 문제는 오랜만에 자바로 알고리즘 과제를 하려고 하니 머리가 하얘져서 자바로 백준을 좀 풀어봐야겠다는 생각으로 선정했다.

이 문제는 경우의 수가 그렇게 많지 않기 때문에 모든 경우의 수를 확인하면서 최댓값을 구하는 방식으로 코드를 짰다.

정답 코드

Java

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

public class Main {
    public static int result=0,n;
    public static boolean[] visited;
    public static int[] temp;
    public static int[] input;
    
    public static void find(int cnt){
        if(cnt==n){ //모든 수 탐색했으면 식 계산
            int sum = 0;
            for(int i=0;i<n-1;i++){
                sum+=Math.abs(temp[i]-temp[i+1]);
            }
            result=Math.max(result,sum); //result 업데이트
            return;
        }
        for(int i=0;i<n;i++){
            if(!visited[i]){
                temp[cnt]=input[i];
                visited[i]=true;
                find(cnt+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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        input = new int[n];
        temp = new int[n];
        visited = new boolean[n];
        
        for (int i = 0; i < n; i++)
            input[i] = Integer.parseInt(st.nextToken());
        find(0);
        System.out.println(result);

    }
}

근데 몇개 글을 읽어보다가 다른 방법도 있다는 것을 알게되었다.

주어진 정수를 정렬해서 순서대로 배열에 넣으면 되는거다.

1) max1 min1

2) min2 max1 min1 max2

3) max3 min2 max1 min1 max2 min3

이런식으로 번갈아가며 앞뒤로 붙여준다.

예를들어 주어진 배열이 1 2 3 4 5 6 이라면

1) 6 1

2) 2 6 1 5

3) 4 2 6 1 5 3

위와 같이 배열을 만들어주면 위의 식을 계산했을 때 최대값이 나온다.

다른 코드

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] input = new int[n];
        for (int i = 0; i < n; i++)
            input[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(input);
        ArrayList<Integer> arr = new ArrayList<>(n);
        int i;
        
        for (i = 0; i < n / 2; i++) { //번갈아가며 배열에 수 추가
            if (i % 2 == 0) {
                arr.add(0, input[n - 1 - i]);
                arr.add(input[i]);
            } else {
                arr.add(0, input[i]);
                arr.add(input[n - 1 - i]);
            }
        }
        
        if(n%2!=0){ //만약 수가 홀수개면 제일 앞,뒤에 넣었을 경우 비교해서 추가
            if(Math.abs(arr.get(0)-input[i])>Math.abs(arr.get(arr.size()-1)-input[i])){
                arr.add(0,input[i]);
            }
            else{
                arr.add(input[i]);
            }
        }
        
        int ans=0;
        for(i=0;i<n-1;i++)
            ans+=Math.abs(arr.get(i)-arr.get(i+1));
        System.out.println(ans);
    }
}