[Baekjoon] 1461번 : 도서관

1. 문제

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

• 그리디 문제

// 문제
세준이는 도서관에서 일한다.
도서관의 개방시간이 끝나서
세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다.
세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다.
각 책들의 원래 위치가 주어질 때,
책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오.
세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다.
책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.
그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

// 입력
첫째 줄에 책의 개수 N과,
세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다.
둘째 줄에는 책의 위치가 주어진다.
N과 M은 50보다 작거나 같은 자연수이다.
책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

// 출력
첫째 줄에 정답을 출력한다.

// 예제 입력 1
7 2
-37 2 -6 -39 -29 11 -28

// 예제 출력 1
131

// 예제 입력 2
8 3
-18 -9 -4 50 22 -26 40 -45

// 예제 출력 2
158

// 예제 입력 3
6 2
3 4 5 6 11 -1

// 예제 출력 3
29

// 예제 입력 4
1 50
1

// 예제 출력 4
1

2. 핵심 아이디어

• 일직선상의 각 책들을 원래의 위치에 놓아야 함
• 0보다 큰 책들과 0보다 작은 책들을 나누어서 처리
• 두 개의 우선순위 큐를 이용하여 문제를 효과적으로 해결할 수 있음
• 마지막 책을 놓을 때는 다시 0으로 돌아올 필요가 없으므로, 가장 먼 책을 마지막으로 놓음

3. Python 문제풀이

import sys
import heapq

n, m = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
positive = []
negative = []

# 가장 거리가 먼 책까지의 거리
largest = max(max(arr), - min(arr))

# 최대 힙을 위해 원소를 음수로 구성
for i in arr :
  # 책의 위치가 양수인 경우
  if i > 0 :
    heapq.heappush(positive, -i)
  # 책의 위치가 음수인 경우
  else :
    heapq.heappush(negative, i)

result = 0

while positive :
  # 한 번에 m개씩 옮길 수 있으므로 m개씩 빼내기
  result += heapq.heappop(positive)
  for _ in range(m - 1) :
    if positive :
      heapq.heappop(positive)

while negative :
  # 한 번에 m개씩 옮길 수 있으므로 m개씩 빼내기
  result += heapq.heappop(negative)
  for _ in range(m - 1) :
    if negative :
      heapq.heappop(negative)

# 일반적으로 왕복 거리를 계산하지만, 가장 먼 곳은 편도 거리 계산
print(-result * 2 - largest)

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    PriorityQueue<Integer> positive = new PriorityQueue<>((p1, p2) -> p2 - p1);
    PriorityQueue<Integer> negative = new PriorityQueue<>((p1, p2) -> p2 - p1);

    st = new StringTokenizer(br.readLine());
    for (int i=0; i<n; i++) {
      int temp = Integer.parseInt(st.nextToken());
      if (temp > 0) {
        positive.offer(temp);
      } else {
        negative.offer(Math.abs(temp));
      }
    }

    int largest = 0;
    if (positive.isEmpty()) {
      largest = negative.peek();
    } else if (negative.isEmpty()) {
      largest = positive.peek();
    } else {
      largest = Math.max(positive.peek(), negative.peek());
    }

    int ans = 0;

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

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

    ans -= largest;
    bw.write(ans + "\n");
    bw.flush();
    bw.close();
    br.close();
  }
}