[BaekJoon] 1461 도서관 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

문제 정리: 양의 방향과 음의 방향으로 책을 가져다 둬야하는데 한번에 M개의 책을 갖고 갈 수 있으며 마지막에는 제자리로 돌아올 필요가 없다.

문제풀이 순서는 다음과 같다.
1. 책을 양의 방향에 있는 책과 음의 방향에 있는 책으로 나눈다.
2. 각 방향에 있는 책들을 정렬하여 멀리 있는 책들부터 거리를 구할 수 있게 한다.
※ 음의 방향은 그대로 정렬, 양의 방향은 내림차순으로 정렬
3. 각 방향에 책이 없어질 때까지 M개의 책을 빼낸다. 책을 빼낼 때 첫번째로 빼는 책은 distance리스트에 저장해둔다.
4. distance리스트를 오름차순으로 정렬하여 가장 큰 값을 제외하고는 x2를 하여 더하고 큰 값은 그냥 더해준다.
※ 최소 걸음수를 구하는 문제이기에 가장 먼 거리를 편도로 이동하고 남은 거리는 왕복으로 이동한다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 총 책의 개수
		int M = Integer.parseInt(st.nextToken()); // 한번에 들 수 있는 책의 개수
		
		ArrayList<Integer> negative = new ArrayList<>(); // 음의 번호에 가야하는 책
		ArrayList<Integer> positive = new ArrayList<>(); // 양의 번호에 가야하는 책
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++) {
			int book = Integer.parseInt(st.nextToken());
			if (book > 0) positive.add(book);
			else negative.add(book);
		}
		Collections.sort(negative);
		Collections.sort(positive, Collections.reverseOrder());
		
		
		ArrayList<Integer> distance = new ArrayList<>();
		// 음의 위치부터 책 정리
		while(!negative.isEmpty()) {
			int temp=0; // 이동해야하는 거리
			temp = negative.remove(0);
			for (int i=1; i<M; i++) {
				if (!negative.isEmpty()) {
					negative.remove(0);
				}
			}
			distance.add(-temp);
		}
		
		// 양의 위치 책 정리
		while(!positive.isEmpty()) {
			int temp=0; // 이동해야하는 거리
			temp = positive.remove(0);
			for (int i=1; i<M; i++) {
				if (!positive.isEmpty()) {
					positive.remove(0);
				}	
			}
			distance.add(temp);
		}
		
		int result = 0;
		Collections.sort(distance); // 가장 먼 거리를 알기 위해 sort
		for (int i=0; i<distance.size(); i++) {
			// 가장 먼 거리만 편도로 이동, 남은 거리는 왕복이라 x2
			if (i == distance.size()-1) result += distance.get(i);
			else result += (distance.get(i)*2);
		}
		
		System.out.println(result);
	}
}