도서관 - 1461

문제

풀이

import java.util.*;

// 도서관 - G5 - 정렬,그리디
public class ex1461 {
    static int n,m;
    static PriorityQueue<Integer> positiveQ = new PriorityQueue<>(Collections.reverseOrder());
    static PriorityQueue<Integer> negativeQ = new PriorityQueue<>(Collections.reverseOrder());
    static int answer=0;

    public static void solution() {
        // 가장 큰 거리는 마지막에 빼줄거임 -> 이유는 마지막은 제자리로 돌아가지 않아도 됨.
        int maxV = 0;
        if(positiveQ.isEmpty()) maxV = negativeQ.peek();
        else if(negativeQ.isEmpty()) maxV = positiveQ.peek();
        else maxV = Math.max(positiveQ.peek(),negativeQ.peek());

        while(!positiveQ.isEmpty()){
            int dis = positiveQ.poll();
            for(int i=0; i<m-1; i++){
                positiveQ.poll();
                if(positiveQ.isEmpty()) break;
            }
            answer+=dis*2;
        }

        while(!negativeQ.isEmpty()){
            int dis = negativeQ.poll();
            for(int i=0; i<m-1; i++){
                negativeQ.poll();
                if(negativeQ.isEmpty()) break;
            }
            answer+=dis*2;
        }

        answer -= maxV;


    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        for(int i=0; i<n; i++){
            int dis = sc.nextInt();
            if(dis>0) positiveQ.offer(dis);
            else negativeQ.offer(Math.abs(dis));
        }

        solution();
        System.out.println(answer);
    }
}

우선 예제 입력 1번을 보자.

7 2
-37 2 -6 -39 -29 11 -28

이렇게 입력받는다. 근데 최소거리는 131인데, 131이 나오려면 내림차순 정렬을 한번하고 가장먼거리인 -39거리는 마지막에 가서 그대로 끝내야하고, 큰거리순으로부터 m만큼의 책의 자리에 책을 한번에 가져다놓고 0의 위치로 돌아와야 최소거리 정답이 나온다.

그렇기 때문에 문제를 해결한 방식은. 어차피 음수양수 한번에 담겨도 결국 따로따로 가져다 놓고 제자리로 돌아오는 원리는 같기 때문에 음수양수를 구분해도된다.

우선순위큐를 음수양수 2가지 타입으로 저장하고. Collections.reverseOrder()로 선언해준다. 이렇게 하면 poll을 했을때 가장 큰수가 먼저 나온다. 그렇게 가장 거리가 먼 순으로 m만큼 poll을 해주면서 제일 처음에 poll을 했던 값을 answer에 *2를 해서 더해준다. 이런 방식으로 두 큐가 Empty 상태일때 까지 while문을 돌려준다.

그리고 마지막에는 제자리로 돌아가지 않아도 되기 때문에 가장 먼거리를 마지막에 가는게 효율적이라서 처음 책의 위치들 중에서 가장 거리가 먼 값을 정답에서 빼준다.