[백준] 1461 도서관 (java)

1. 문제

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

 

2. 풀이

- 키워드: 그리디를 이용해서 닥치는대로 풀어야한다.

 

주어진 책의 위치 리스트는 다음과같다. 

-37

2

-6

-39

-29

11

-28

 

여기서 세준이의 위치와 책들의 시작위치는 0 이기 때문의 0의 위치도 추가된다.

최소 거리를 구하기 위해서는 양수와 음수를 차례대로 정렬해보아야 한다.

-39

-37

-29

-28

-6

0

2

11

 

0 의 위치에서부터 M 만큼의 책을 들고 책을 두러 이동할 수 있다. 

음수쪽에서 이동하게 되면 예제 1 (최대 들고 갈 수 있는 책의 수:2) 을 예로 들면 아래 처럼 묶어서 가는 것 보다는 

최소 걸음수 : 169

 

제일 큰수를 최대한 묶음으로 가는 것이 최소 걸음 수가 나오게 된다.

최소 걸음수 : 109

주의할 점은 제일 마지막으로 도착한 위치에서는 다시 0 의 위치로 돌아오지 않고 끝내도 된다는 것이다.

따라서 바로 위의 표를 식으로 만들면

 

(6 * 2) + (29 * 2) + 39 (마지막) = 109 

 

로 음수 방향에서의 최소 걸음수를 구할 수 있게 된다.

 

가장 큰수가 묶음으로 가는 것이 최소 걸음수를 구할 수 있기 때문에 양수 리스트와 음수 리스트를 따로 구현하여 서로의 절대값으로 내림차순한 뒤 최소 걸음수를 구해야한다. 

 

주의!

이 때, 코드를 작성할 때 우선순위큐를 이용해서 풀 수 있는데 음수인 경우 절대값으로 큐에 집어넣으면 원하는대로 정렬할 수 있다.

그런데 한가지 주의할 점은 계속해서 원하는대로 정렬이 되지 않아서 chatGPT 에게 물어봤는데 우선순위큐의 경우 힙 구조로 작동하기 때문에 큐에서 값을 꺼낼 때 원하는 정렬 순서를 보장한다고 한다.  (주의!)

3. 소스코드

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

/**
 * https://www.acmicpc.net/problem/1461 걸을 수 있는 최소 걸음 수 구하
 */
public class BG_도서관 {

  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> positiveQ = new PriorityQueue<>((p1, p2) -> p2 - p1);
    PriorityQueue<Integer> negativeQ = 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) { // 양수라면
        positiveQ.offer(temp);
      } else { // 음수라면
        negativeQ.offer(Math.abs(temp));
      }
    }

    int maxPosition = 0; // 가장 멀리있는 책의 위치를 저장
    if (positiveQ.isEmpty()) {
      maxPosition = negativeQ.peek();
    } else if (negativeQ.isEmpty()) {
      maxPosition = positiveQ.peek();
    } else {
      maxPosition = Math.max(positiveQ.peek(), negativeQ.peek()); // 두개의 최상위 원소중 가장 큰 값을 지정
    }

    int result = 0;

    while (!positiveQ.isEmpty()) { // 우선순위큐에 값이 없을 때까지
      int temp = positiveQ.poll();
      for (int i = 0; i < M-1; i++) {
        positiveQ.poll();

        if (positiveQ.isEmpty()) {
          break;
        }
      }

      result += temp * 2;
    }

    // 39 37 29 28 6
    while (!negativeQ.isEmpty()) {
      int temp = negativeQ.poll();
      for (int i = 0; i < M-1; i++) {
        negativeQ.poll();

        if (negativeQ.isEmpty()) {
          break;
        }
      }

      result += temp * 2;
    }

    result -= maxPosition; // 마지막에 제일 큰 위치의 수를 뺀다.
    bw.write(result + "\n");
    bw.flush();
    bw.close();
    br.close();
  }
}