백준|1461번|도서관

문제설명
도서관에 있는 책들의 원래 위치와 최대 들고갈 수 있는 책의 개수를 입력받고 모든 책을 제자리에 갖다 놓는데 필요한 최소한의 이동거리를 구하는 문제입니다.(마지막 책을 가져다놓은 뒤에는 원래 위치로 돌아올 필요가 없고, 책의 위치는 -10000<=책의 위치<=10000입니다.)

작동 순서
1. 원래 위치로 되돌려놔야할 책들의 개수와 한번에 들고 갈 수 있는 책의 개수를 입력받습니다.
2. 책들의 원래 위치를 입력받고 이를 정렬한 뒤 양수와 음수로 분리합니다.
3. 양수의 최장 이동거리와 음수의 최장 이동거리를 비교하고 더 긴거리는 이동거리에 1배만 더해주고 더 짧은거리는 2배(가져다놓으러 가는 거리+원래 위치로 돌아오는 거리)를 더해줍니다.(거리가 더 먼 곳에 있는 책은 가져다놓은뒤 정리를 끝내고 더 짧은 거리에 있는 책은 가져다놓은뒤 원래 위치로 복귀합니다. 이것이 코드에서는 최초의 행위이지만 실제 책을 가져다놓는 작업에서는 마지막행위이므로 돌아올 필요가 없습니다.)
4. 남은 책들은 최대 개수씩 가져다놓으며 가져다놓는 책들의 위치중 가장 먼 거리의 2배를 이동거리에 더해줍니다.(이렇게하면 가장 멀리있는 책과 그 다음으로 멀리있는 책들을 함께 가져다놓기 때문에 남은 책들은 앞에서 가져다놓은 책보다 거리가 작거나 같습니다.)
5. 모든 정리가 끝나면 이동거리를 출력합니다.

소스코드

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

public class 백준_1461번_도서관 {
    static int walking(Queue<Integer> q, int M){
        int distance;
        int book=1;
        int walk=0;
        while(!q.isEmpty()){
            distance=q.poll();
            if(book==1) {
                walk+=distance*2;
            }
            if(book==M) book=1;
            else book++;
        }
        return walk;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        Queue<Integer> positive =new LinkedList<>();
        Queue<Integer> negative =new LinkedList<>();
        int N=Integer.parseInt(st.nextToken()), M=Integer.parseInt(st.nextToken());
        int[] num=new int[N];
        int walk=0, negMax, posMax;
        st=new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            num[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(num);
        for(int i=N-M-1;i>=0;i--){
            if(num[i]<0) break;
            positive.add(num[i]);
        }
        for(int i=M;i<N;i++){
            if(num[i]>0) break;
            negative.add(-num[i]);
        }
        if(num[0]>0) negMax=0;
        else negMax=-num[0];
        if(num[N-1]<0) posMax=0;
        else posMax=num[N-1];
        walk+=Math.min(posMax, negMax)*2+Math.max(posMax, negMax)+walking(positive, M)+walking(negative, M);
        System.out.print(walk);
    }
}

후기
오랜만에 풀어본 그리디 문제인데 푸는데 꽤나 오래걸렸습니다. 코드를 짤 때 가까운 범위부터 처리를 해서 오답이 나왔었는데 실제 작업과 달리 먼거리 부터 계산하고 나니 정답을 맞출 수 있었습니다. 컴퓨팅적 사고 능력을 계속해서 길러야 할 것 같습니다.