[BOJ 그리디] 도서관 1461.JAVA

문제 링크 : https://www.acmicpc.net/problem/1461

1461번: 도서관

문제 풀이

1. 음수의 책의 거리와 양수의 책의 거리를 각 리스트에 삽입한다.
2. 절댓값으로 가장 멀리 있는 책의 위치를 찾는다.
3. 각 리스트를 내림차순으로 정렬한다.
4. 옮길 수 있는 최대 책의 수만큼 책을 들고 가장 멀리 있는 책의 위치를 계산한다.
5. 옮길 수 있는 최대 책의 수 보다 작은 수의 책이 남았을 경우 남아 있는 책 중 가장 멀리 있는 책의 위치를 계산한다.
6. 계산된 거리에서 가장 멀리 있는 책의 위치를 빼준다.

아래와 같이 소스 공유 합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 도서관 {
    public static int max, num, res, farthest;
    public static List<Integer> plusList = new ArrayList<>();
    public static List<Integer> minusList = new ArrayList<>();
    // 음수와 양수 구분하여 정렬
    public static Comparator<Integer> compare = new Comparator<Integer>() {

        @Override
        public int compare(Integer o1, Integer o2) {
            if(o1 > 0 && o2 > 0) {
                return (o1 > o2) ? -1:(o1 == o2) ? 0:1;
            }

            return (o1 > o2) ? 1:(o1 == o2) ? 0:-1;
        }
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strs = br.readLine().split(" ");

        num = Integer.parseInt(strs[0]);
        max = Integer.parseInt(strs[1]);
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        while(st.hasMoreTokens()) {
            int val = Integer.parseInt(st.nextToken());
            if(val > 0) plusList.add(val);
            if(val < 0) minusList.add(val);
            // 가장 먼 거리를 구하여 모든 계산이 끝난 후 뺄셈을 한다.
            farthest = Math.max(farthest, Math.abs(val));
        }

        Collections.sort(plusList, compare);
        Collections.sort(minusList, compare);

        int cnt = 0;

        for(int i = 0; i < plusList.size(); i += cnt) {
            // 이동 횟수 초기화
            cnt = 0;
            int select = 0;
            for(int j = 0; j < max; j++) {
            	// 최대로 옮길 수 있는 책의 수 보다 작은 개수가 남았을 경우
                if(i + j < plusList.size()) {
                    select = Math.max(select, Math.abs(plusList.get(i + j)));
                    cnt++;
                }
            }
            res += select * 2;
        }

        for(int i = 0; i < minusList.size(); i += cnt) {
            // 이동 횟수 초기화
            cnt = 0;
            int select = 0;
            for(int j = 0; j < max; j++) {
            	// 최대로 옮길 수 있는 책의 수 보다 작은 개수가 남았을 경우
                if(i + j < minusList.size()){
                    select = Math.max(select, Math.abs(minusList.get(i + j)));
                    cnt++;
                }
            }
            res += select * 2;
        }

        System.out.println(res - farthest);
    }
}

---

그리디 문제에 대한 경험이 부족하여 스터디에서 그리디 문제를 풀자고 요청하였다.
스터디를 진행하는 3시간 동안 문제를 풀지 못하였다. 역시나 어려웠다.
그래서 힌트를 받았지만 받은 풀이를 그대로 구현하기는 싫었다.
지금 당장 풀지 못하더라도 내가 스스로 고민하고 내가 생각한 로직대로 풀고 싶었고 그 노력이 이 문제를 내 것으로 만들어줄 것이라고 믿었다.
스터디 끝나고 집에 돌아와 반례를 보고 나서 문제를 맞힐 수 있었다.

부족한 실력 때문에 자존심이 많이 상해서 주저리 적었습니다.

읽어주셔서 감사합니다.