[JAVA] 백준 1092 도서관_구현

 

문제 : 

https://www.acmicpc.net/problem/1461

접근 : 

 

  - CASE 1 : 마지막에 돌아올 필요가 없으므로 +와 - 방향 중 긴 쪽을 2번째로 이동한다.

 

  - CASE 2 : + 또는 - 한쪽 방향만 존재 할 경우, 1번째 이동은 없다고 보고 2번째 이동을 하는 것 처럼 처리한다.
   (돌아올 필요가 없으므로 2번째에 해당) 

 

  - CASE 3 : 첫 번째 방향을 이동할 때는 가장 먼 곳부터, 방향 전환이 일어나기 전까지 가장 먼곳을 기준으로 이동한다.

 

  - CASE 4 : 두 번째 방향을 이동할 때는 가장 먼 곳을 기준으로 m 등분 하여 최소가 되는 걸음 수 로 움직인다.

 

  - CASE 5 : 두 번째 방향 이동 후, 돌아올 필요가 없으므로 돌아오는 걸음 수를 계산하지 않는다.

 

 

 

 

 

코드 구현 : 

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

public class Main {
    private static int move(List<Integer> first, List<Integer> second, int m){
        int ans = 0 ;
        if(!first.isEmpty()){
            first.sort(Comparator.reverseOrder());
            for(int i = 0 ; i < first.size() ; i += m) ans += 2 * first.get(i);
        }
        //가장 먼곳을 대상으로 하면 최소가 되므로 먼 곳부터 연산 
        second.sort(Comparator.naturalOrder());
        for(int i = second.size()-1  ; i >= 0; i -= m) ans += 2 * second.get(i);
        
        //마지막 1번은 돌아올 필요가 없으므로 걸음 수 차감
        ans -= second.get(second.size()-1);
        return ans;
    }

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

        String[] inputs =  br.readLine().split(" ");
        int n = Integer.parseInt(inputs[0]);
        int m = Integer.parseInt(inputs[1]);

        String[] books = br.readLine().split(" ");
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        int max_left = 0;
        int max_right = 0;

        for(int i = 0 ; i < books.length ; i++) {
            int a = Integer.parseInt(books[i]);
            if(a < 0) {
                max_left = Math.max(max_left, -1 * a);
                left.add(-1 * a);
                continue;
            }
            max_right = Math.max(max_right, a);
            right.add(a);
        }

        boolean is_left_start = max_left > max_right;

        List<Integer> first;
        List<Integer> second;
        
        //먼저 가져다 놓을 방향의 리스트 설정
        if(is_left_start) {
            first = right;
            second = left;
        }else{
            first = left;
            second = right;
        }
        System.out.println(move(first, second, m));
        br.close();
    }
}