백준 1461 도서관 (JAVA)

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

1461번: 도서관

 

문제설명

0인 곳에서 돌아다니면서 책을 알맞은 위치까지 가져가야 합니다. 위 예제를 풀어보면 

{-39, -37}, {-29, -28}, {-6}, {2, 11}로 총 22 + 12 + 58 + 39 = 131입니다.

 

문제에 대한 아이디어

• 처음에는 0에서 가까운 부분 부터 배달을 해야 하지 않을까?라는 고민을 했습니다. 하지만 경우의 수가 너무 많아져 복잡해집니다. 그래서 먼 곳부터 배달을 하는 방법을 생각해 봤습니다. 어차피 먼 곳에 배달을 해야 하니깐 먼 곳부터 m만큼 배달을 하는 것입니다. 
• 두 번째 문제는 -6 만 선택하는 부분입니다. 두 곳씩 배달하다 보면 -6과 -28을 배달하게 될 것입니다. 그래서 음수의 먼 곳 양수의 먼 곳을 따로 생각해서 풀었습니다.
• 마지막은 다시 안돌아와도 된다는 것을 해결해줘야 합니다. 양수에서 제일 큰 숫자, 음수에서 제일 큰 숫자를 비교해 더 큰 숫자를 마지막 합에서 빼주면 답이 됩니다.

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> minusPq = new PriorityQueue<>();
        PriorityQueue<Integer> plusPq = new PriorityQueue<>((c1,c2) -> {
            return c2 - c1;
        });
        st = new StringTokenizer(buf.readLine());
        for(int i = 0; i < n; ++i){
            int num = Integer.parseInt(st.nextToken());
            if(num < 0) minusPq.add(num);
            else plusPq.add(num);
        }
        int answer = 0;
        int num = 0;
        // 더 먼 곳 선택
        if(plusPq.size() > 0 && minusPq.size() > 0) num = Math.max(Math.abs(minusPq.peek()), plusPq.peek());
        else {
            if(plusPq.size() > 0) num = plusPq.peek();
            else num = Math.abs(minusPq.peek());
        }
        // 음수 부분
        while(!minusPq.isEmpty()){
            for (int i = 0; i < m; ++i) {
                    int temp = minusPq.poll();
                    if (i == 0) answer += (Math.abs(temp) * 2);
                    if(minusPq.isEmpty()) break;
            }
        }
        // 양수 부분
        while(!plusPq.isEmpty()){
            for (int i = 0; i < m; ++i) {
                int temp = plusPq.poll();
                if (i == 0) answer += (Math.abs(temp) * 2);
                if(plusPq.isEmpty()) break;
            }
        }
        answer -= num;
        System.out.println(answer);
    }
}

https://github.com/SeWooooong/CodingTest_Practice/tree/main/%EB%B0%B1%EC%A4%80/Gold/1461.%E2%80%85%EB%8F%84%EC%84%9C%EA%B4%80