[BOJ] 백준 10819 차이를 최대로

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

 Input 

6

20 1 15 8 4 10

 

 Output 

62

배열 A 원소 순서를 적절히 바꿔 다음 식의 최댓값을 구하시오.

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

 

구현

|A[0] - A[1]| + |A[1] - A[2]|의 최대값을 구하기 위해서는

A[1] 기준으로 양 옆에 최솟값 최대값을 배치하는 것입니다.

 

주어진 Sample을 풀이하면 다음과 같습니다.

 → |10 - 4| + |4 - 20| + |20 - 1| +  |1 - 15| +  |15 - 8| 

= 6 + 16 + 19 + 14 + 7 = 62

즉, 전체 수식에서 마찬가지로 가장 가운데를 기준으로 채워갑니다.

① 20max - 1min    / 남은 숫자: { 15 10 8 4 }

② 4min -20 - 1 - 15max    / 남은 숫자: { 10 8 }

③ 10max - 4 -20 - 1 - 15 - 8min  / 남은 숫자: {  }

남은 숫자에서 최대값과 최솟값을 교대로 앞뒤에 배치

 

원소의 개수가 홀수개인 경우, 마지막에 배치하는 숫자는 

앞, 뒤 중 좀 더 차이를 내는 곳에 배치합니다. 

{ 9 10 4 20 1 15 8} or { 10 4 20 1 15 8 9 }

---

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
 
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
         
        List<Integer> list = new LinkedList<>();
         
        for(int i=0; i<N; i++) {
            list.add(Integer.parseInt(sc.next()));
        }
         
        Collections.sort(list);
         
        // 홀수 개수인지 확인
        boolean isOdd =  (N % 2 != 0) ? true : false;
         
        // 기존의 홀수개이면 짝수개가 되도록 일단 setting
        int temp_N = isOdd ? N-1 : N;
         
        DQueue DQ = new DQueue();
         
        boolean flag = true;
        // 앞뒤로 교대로 해서 넣는다.
        for(int i=0; i<temp_N; i=i+2) {
            if(flag) {
                DQ.insertFront(list.remove(list.size()-1));
                DQ.insertRear(list.remove(0));
            }else {
                DQ.insertRear(list.remove(list.size()-1));
                DQ.insertFront(list.remove(0));
            }
            flag = !flag;
        }
         
         
        // 기존에 홀수개 였다면 아직 숫작 한개가 남아 있으므로 양끝을 비교해서 삽입한다.
        if(isOdd) {
            int lastNode = list.remove(0);
            if(Math.abs(DQ.front.data - lastNode) > Math.abs(DQ.rear.data - lastNode) ) {
                DQ.insertFront(lastNode);
            }else {
                DQ.insertRear(lastNode);
            }
        }
         
        DQ.findAnswer();
    }
}
 
 
class DQNode{
     
    int data;
    DQNode left;
    DQNode right;
     
    public DQNode(int data) {
        this.data = data;
    }
}
class DQueue{
    DQNode front;
    DQNode rear;
     
     
     
    // 앞으로 삽입
    void insertFront(int data) {
        DQNode node = new DQNode(data);
        // 비어있다면(처음 넣는 단계라면)
        if(isEmpty()) {
            front = node;
            rear = node;
            return;
        }
        // 제일 앞에 있던 노드는 뒤로 밀려나야 한다.
        node.right = front;
        front.left = node;
        front = node;
    }
     
     
    // 뒤로 삽입
    void insertRear(int data) {
        DQNode node = new DQNode(data);
        // 비어있다면(처음 넣는 단계라면)
        if(isEmpty()) {
            front = node;
            rear = node;
            return;
        }
        // 제일 뒤에 있던 노드가 앞으로 밀려난다.
        node.left = rear;
        rear.right = node;
        rear = node;
    }
     
    // 비어있는지 확인
    boolean isEmpty() {
        return (front == null || rear == null);
    }
     
    void printDQueue() {
        // 앞에서(front) 부터 출력하겠다.
        DQNode printNode = front;
        if(isEmpty()) {
            System.out.println("Empty!");
            return;
        }
         
        while(printNode != null) {
            System.out.print(printNode.data + " ");
            printNode = printNode.right;
        }
    }
     
    void findAnswer() {
        DQNode tempNode = front;
        int sum = 0;
        // 사실 문제조건상 덱이 비워져 있는 경우는 없다
        while(tempNode != null) {
            if(tempNode.right != null) {
                sum += Math.abs(tempNode.right.data - tempNode.data);
            }
            // 뒤로(rear쪽으로) 이동
            tempNode = tempNode.right;
        }
        System.out.println(sum);
    }
}