[BaekJoon] 1461 도서관

1.  문제 링크

2.  문제

요약

• 세준이가 현재 0의 위치에 있고 0의 위치에 사람들이 마구 놓은 책들이 있는데 이 책들을 원래 위치로 돌려놓으려고 합니다.
• 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 필요한 최소 걸음 수를 계산하는 문제입니다.
• 세준이는 한 걸음에 1칸씩 갈 수 있고 각 책의 위치는 정수 좌표이며 마지막 책을 돌려놓은 후에는 다시 돌아오지 않아도 됩니다.
• 입력: 첫 번째 줄에 50보다 작거나 같은 자연수인 책의 개수 N, 50보다 작거나 같은 자연수인 세준이가 한 번에 들 수 있는 책의 개수 M이 주어지고, 두 번째 줄에는 0이 아니고 절댓값은 10,000보다 작거나 같은 정수인 책의 위치들이 주어집니다.
• 출력: 책을 모두 제자리에 놔둘 때 필요한 최소 걸음 수를 출력합니다.

3.  소스코드

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

public class Main {
	static int[] bookPlace;
	
	public int getMinWalkNum(int max_book) {
		if(bookPlace.length == 1) {
			return Math.abs(bookPlace[0]);
		}
		Arrays.sort(bookPlace);
		if(bookPlace.length <= max_book) {
			if(bookPlace[0] * bookPlace[bookPlace.length - 1] < 0) {
				if(Math.abs(bookPlace[0]) > bookPlace[bookPlace.length - 1]) {
					return Math.abs(bookPlace[0]) + bookPlace[bookPlace.length - 1] * 2;
				} else {
					return Math.abs(bookPlace[0]) * 2 + bookPlace[bookPlace.length - 1];
				}
			} else {
				return Math.abs(bookPlace[bookPlace.length - 1]);
			}
		}
		PriorityQueue<Integer> negative = new PriorityQueue<Integer>();
		PriorityQueue<Integer> positive = new PriorityQueue<Integer>(Collections.reverseOrder());
		for(int i = 0; i < bookPlace.length; i++) {
			if(bookPlace[i] < 0) {
				negative.offer(bookPlace[i]);
			} else {
				positive.offer(bookPlace[i]);
			}
		}
		int max_distance = 0;
		if(negative.isEmpty()) {
			max_distance = positive.peek();
		} else if(positive.isEmpty()) {
			max_distance = Math.abs(negative.peek());
		} else {
			max_distance = Math.max(positive.peek(), Math.abs(negative.peek()));
		}
		int distance = 0;
		while(positive.size() > 0) {
			int temp = positive.peek();
			for(int i = 0; i < max_book; i++) {
				positive.poll();
				if(positive.isEmpty()) {
					break;
				}
			}
			distance += (temp * 2);
		}
		while(negative.size() > 0) {
			int temp = negative.peek();
			for(int i = 0; i < max_book; i++) {
				negative.poll();
				if(negative.isEmpty()) {
					break;
				}
			}
			distance += (Math.abs(temp) * 2);
		}
		distance -= max_distance;
		return distance;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int book_num = Integer.parseInt(input[0]);
		int max_book = Integer.parseInt(input[1]);
		bookPlace = new int[book_num];
		input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < book_num; i++) {
			bookPlace[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		bw.write(m.getMinWalkNum(max_book) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• M개의 책을 한 번에 들 수 있어 M개 중에서 가장 먼 곳의 좌표를 찍는다면 M개의 책을 모두 제자리에 놓을 수 있기 때문에 이를 인접한 M개의 책들은 같이 들어서 제자리에 놓도록 하고 먼 곳의 책들부터 가져다놓아야 합니다.
• 예를 들어, -18, -9, -4, -26, -45, 50 이렇게 6개의 좌표가 주어져있고 2개의 책을 한 번에 들 수 있을 때, 음수 쪽의 좌표만 본 경우
  • (-4, -9), (-18, -26), (-45) 이러한 방식으로 들고 간다면 걸음수는 9 * 2 + 26 * 2 + 45 * 2 = 160이 되는데
  • (-4), (-9, -18), (-26, -45) 이러한 방식으로 들고 간다면 걸음수는 4 * 2 + 18 * 2 + 45 * 2 = 134가 되어 가까운 쪽부터 제자리에 놓는 것보다 더 적은 걸음수로 제자리에 가져다 놓을 수 있습니다.
• 만약 음수 좌표의 책과 양수 좌표의 책을 같이 들고 있다면 한 쪽 좌표로 간 후에 다시 0으로 돌아와 다른 쪽 좌표로 가야하는 상황이기에 어차피 각 좌표를 따로 가는 것과 같은 값이 나오므로 들어온 책의 좌표를 음수와 양수로 나눠서 문제 풀이를 진행합니다.
• 책이 한 권이라면 해당 좌표까지의 절댓값이 최소 걸음수가 됩니다.
• 책의 개수보다 한 번에 들 수 있는 책의 개수가 더 많거나 같다면 아래 3가지 경우에 따라 답이 결정됩니다.
1. 모든 책의 좌표가 음수 또는 양수일 때
• 모든 책의 좌표 중에서 절댓값이 제일 큰 책의 좌표의 절댓값이 최소 걸음수가 됩니다.
2. 책의 좌표가 음수와 양수 모두 포함하고 있을 때
• 음수 좌표에서 절댓값이 제일 큰 좌표와 양수 좌표에서 절댓값이 제일 큰 좌표의 절댓값을 비교하여 작은 쪽을 먼저 방문한 후에 0으로 돌아와서 큰 쪽으로 진행하는 것이 최소 걸음수가 됩니다.
• 위 방법들을 이용하여 문제를 풀어갑니다.

1. 입력받은 책의 수가 한 권이라면 해당 책의 좌표의 절댓값이 문제의 답이 되므로 이를 출력합니다.
2. 만약 입력받은 책의 수보다 한 번에 들 수 있는 책의 수가 더 많거나 같다면 위에서 말씀드린 방식으로 걸음수를 구하여 해당 걸음수를 출력합니다.
3. 만약 위 두 경우 모두 아니라면 음수와 양수를 저장하기 위한 negative와 positive PriortyQueue를 2개 생성하고 책의 좌표가 양수인 것은 positive에, 음수인 것은 negative에 저장하는데 절댓값이 높은, 즉 0으로부터 거리가 더 먼 책들이 우선이 될 수 있도록 positive는 내림차순으로, negative는 오름차순으로 정렬합니다.
4. 마지막에 제자리에 가져다 놓는 책은 다시 0으로 돌아올 필요가 없으므로 걸음수를 줄이기 위해서는 가장 거리가 먼 책을 가장 나중에 제자리에 가져다 놓아야 하기 때문에 negative에서 뽑아낸 수와 positive에서 뽑아낸 수 중 더 절댓값이 높은 수의 절댓값을 max_distance라는 변수에 저장합니다. 이는 좌표의 절댓값에 2를 곱하여 걸음수를 계산할 것인데 max_distance는 한 번만 가면 되기 때문에 가장 마지막에 한 번 빼주기 위해 만들어주었습니다.
5. positive와 negative 두 PriorityQueue 모두 더 이상 Queue에 값이 없을 때까지 가장 절댓값이 큰 값을 각각 뽑아내어 절댓값에 2를 곱하여 현재까지 걸은 걸음수에 더해주고 한 번에 들 수 있는 책의 개수만큼 Queue에서 데이터를 제거해줍니다. 만약 제거해주다가 더 이상 Queue에 데이터가 없다면 이 때 또한 작업을 중지합니다.
6. 이렇게 계산한 걸음수에서 max_distance를 빼주면 최소 걸음수가 나오고 이를 출력합니다.