백준 1461번 : 도서관 java

이 문제는 정렬을 이용하여 푸는 그리디 알고리즘 문제입니다.

이 문제를 풀기 위해서 저는 입력받은 값들을 하나의 List에 넣어 정렬할 후 처음 인덱스에 들어있는 인자와 마지막에 있는 인자의 절댓값을 비교하여 절댓값이 큰 쪽이 앞에 오게 정렬했습니다.

그리고 M개만큼 수를 List의 0번 인덱스에서 remove하면서 출력 값 answer에 더해주었고 remove 한 값에서 부호가 바뀔 경우에는 이 List를 뒤집어서 위의 과정을 반복했습니다.

---

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

public class Main {
    public static void main(String[] args) throws IOException{
        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());

        List<Integer> l = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++)
            l.add(Integer.parseInt(st.nextToken()));

        Collections.sort(l);

        //l의 앞에 절댓값이 더 큰 값들이 오게 함
        if(Math.abs(l.get(0)) < Math.abs(l.get(l.size()-1)))
            Collections.reverse(l);

        int cnt = 0;
        //음수 양수가 바뀔 경우 다시 뒤집어서 처리
        boolean changed = false;

        int num = 0;
        while(!l.isEmpty()){
            int firstNum = 0;
            for(int i = 0; i<M; i++) {
                int first = l.remove(0);

                if(i == 0)
                    firstNum += first;

                if (l.isEmpty())
                    break;

                //second에서 first와 부호가 바뀌었는지 확인
                int second = l.remove(0);
                l.add(0, second);

                //음수 양수가 바뀔 때
                if ((first < 0 && second > 0) || (first > 0 && second < 0)) {
                    changed = true;
                    break;
                }
            }
            //가장 멀리 있는 책을 정리하여 다시 오지 않아도 될 때
            if (num == 0)
                cnt += Math.abs(firstNum);
            //다시 0으로 돌아와야 할 때
            else
                cnt += Math.abs(firstNum) * 2;

            num++;
            if(changed)
                break;
        }

        //부호가 바뀌었을 경우 다시 절댓값이 큰 쪽이 앞에 오게 함
        if(changed) {
            Collections.reverse(l);

            while(!l.isEmpty()){
                int firstNum = 0;
                for(int i = 0; i<M; i++) {
                    int first = l.remove(0);

                    if(i == 0)
                        firstNum = first;
                    if (l.isEmpty())
                        break;
                }

                //부호가 바뀔 경우 무조건 0으로 돌아와야 함
                cnt += Math.abs(firstNum) * 2;
            }
        }

        System.out.println(cnt);
    }
}