문제

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

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

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

링크텍스트

접근

처음 보자마자 접근 방식은 떠올렸으나 , 구현의 미숙으로 상당히 헤맸던 문제다.

먼저, 입력값을 양수/음수로 나누고 양수의 최대값과 음수의 절대값의 최대값을 비교한다.

양수가 더 크게 나왔다면 책을 넣는 진행 방향은 음수->양수이고, 음수라면 그 반대이다. (마지막으로 제일 멀리 간 뒤 돌아오지 않기 위해)

진행 방향이 정해졌다면, 그 중 0에서 가장 먼 값부터 시작하여 m개씩 반납한다. 이동거리는 가장 먼 값의 절대값 x 2이다. 해당 부호에서 남은 책이 m권 보다 적다면 이때도 현재 남은 가장 먼 값의 절대값 x 2를 이동거리에 더해준다.

한쪽 부호가 끝났다면 다른쪽 부호도 마찬가지로 반납한다. 허나 가장 멀리 가서 반납한 뒤 거기서 이동이 끝나므로, 진행 방향의 가장 먼 값을 한번 빼준다. (먼 값의 절대값 x 2를 거리에 계속 더해줬으므로)

코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		boolean dir; // false 음수방향 true 양수방향
		int countMinus = 0;
		int countPlus = 0;
		int result = 0;
		
		int [] tmp = new int[n];
		for(int i = 0; i < n; i++) {
			tmp[i] = sc.nextInt();
			if(tmp[i] > 0)
				countPlus++;
			else
				countMinus++;
		}
		Arrays.sort(tmp);
		
		Integer[] bookPlus = new Integer[countPlus];
		int[] bookMinus = new int[countMinus];
		
		for(int i = 0; i < countMinus; i++)
			bookMinus[i] = tmp[i];
		int x = 0;
		for(int i = countMinus; i < n; i++)
			bookPlus[x++] = tmp[i];

		
		if (countPlus == 0) {
			Arrays.sort(bookMinus);
			dir = false;
		} else if (countMinus == 0) {
			Arrays.sort(bookPlus, Collections.reverseOrder());
			dir = true;
		} else {
			Arrays.sort(bookPlus, Collections.reverseOrder());
			Arrays.sort(bookMinus);
			dir = bookPlus[0] > Math.abs(bookMinus[0]) ? true : false;
		}

		if (dir) {
			int now = 0;
			while (countMinus >= m) {
				result += Math.abs(bookMinus[now]) * 2;
				countMinus -= m;
				now += m;
			}

			if (countMinus > 0) {
				result += Math.abs(bookMinus[now]) * 2;
			}
			
			now = 0;
			while (countPlus >= m) {
				result += bookPlus[now] * 2;
				countPlus -= m;
				now += m;
			}
			
			if(countPlus > 0) {
				result += bookPlus[now] * 2;
			}
			result -= bookPlus[0];

		} else {
			int now = 0;
			while (countPlus >= m) {
				result += bookPlus[now] * 2;
				countPlus -= m;
				now += m;
			}
			
			if(countPlus > 0) {
				result += bookPlus[now] * 2;
			}
			
			now = 0;
			while (countMinus >= m) {
				result += Math.abs(bookMinus[now]) * 2;
				countMinus -= m;
				now += m;
			}

			if (countMinus > 0) {
				result += Math.abs(bookMinus[now]) * 2;	
			}
			result -= Math.abs(bookMinus[0]);
		}

		System.out.println(result);
	}
}

---

그리디 알고리즘에 관한 문제라 훨씬 더 간단한 풀이가 있을것같다. 정답까지 하나하나 더듬으며 짠 코드라 깔끔하지 못한게 상당히 아쉽다.

문제의 요점은 먼 값 부터 m개씩 짝지어 반납하되, 가장 먼 값은 돌아오는 것을 고려하지 않아도 되고, 반납하는 순서도 중요하지 않다.