[BOJ] 백준 1461 - 도서관 (자바)

시뮬레이션....,,

아이디어는 간단한다. 거리 먼 M개씩 묶어 거리를 합친다. 최종적으로 합친 거리에서 가장 멀었던 거리를 뺀다.

나는 음수와 양수를 나눠서 계산했다.

범위가 작았기에 가능했지만 내가 구현한것은 성능 상 나쁜구현인거 같다.

풀이

1. 양수와 음수를 저장할 우선순위 큐를 사용한다. (우선순위큐를 사용하면 정렬되서 pop 할수 있기 때문에 사용했다)

2. 음수 우선순위큐와 양수 우선순위큐에서 따로 실행한다. 

3. 큐가 빌 때까지 M만큼 계속해서 뺀다. (즉 음수나 양수에 있는 모든 책을 가져오는 것)

4. 그때 가장 맨처음 나온게 이번에 이동했을 때의 가장 먼 거리를 갖고 있으므로 그때만 전체 길이에 추가해준다.

5. 전체길이에 추가할 때마다 전체 최장 거리를 저장해준다.

6. 전체 길이에서 최장 이동 거리를 뺀다.

7. 끝;; 설명 진짜 못한다.

소스

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
 
    public static void main(String args[]) throws Exception {
        // BufferedReader br = new BufferedReader(new
        // InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
        String[] str = br.readLine().split(" ");
 
        int N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        str = br.readLine().split(" ");
        
        //양수와 음수를 나눠서 계산
        Queue<Integer> pos_q = new PriorityQueue<Integer>((x, y) -> y - x);
        Queue<Integer> neg_q = new PriorityQueue<Integer>();
 
        for (int i = 0; i < N; i++) {
            if (Integer.parseInt(str[i]) > 0) {
                pos_q.add(Integer.parseInt(str[i]));
            } else {
                neg_q.add(Integer.parseInt(str[i]));
 
            }
        }
        int element;
        int max = 0;
        int sum = 0;
        //양수가 없을때까지 
        while (!pos_q.isEmpty()) {
            //한번의 이동에 M개의 책을 가져올 수 있다.
            for (int i = 0; i < M; i++) {
                //M개씩 가져오다보면 마지막에 M개보다 부족 할 수 있기 때문에 continue 함수를 써서 넘어간다.
                //continue 안하면 에러
                if (pos_q.isEmpty())
                    continue;
                element = pos_q.poll();
 
                //처음 가는 곳이 제일 거리가 먼곳이므로 이때만 거리를 더해주면 된다.
                if (i == 0) {
                    sum += Math.abs(element);
                    if (Math.abs(element) > max) {
                        max = Math.abs(element);
                    }
                }
            }
        }
        //음수 일때
        while (!neg_q.isEmpty()) {
            //한번의 이동에 M개의 책을 가져올 수 있다.
            for (int i = 0; i < M; i++) {
                //M개씩 가져오다보면 마지막에 M개보다 부족 할 수 있기 때문에 continue 함수를 써서 넘어간다.
                //continue 안하면 에러
                if (neg_q.isEmpty())
                    continue;
                element = neg_q.poll();
                
                //처음 가는 곳이 제일 거리가 먼곳이므로 이때만 거리를 더해주면 된다.
                if (i == 0) {
                    sum += Math.abs(element);
                    if (Math.abs(element) > max) {
                        max = Math.abs(element);
                    }
                }
            }
        }
        System.out.println(sum * 2 - max);
    }
}