[백준 - 1461][GOLD 4][해설 X] - 도서관 (JAVA)

문제 링크

---

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

 

문제

---

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

 

입력

---

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

 

출력

---

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

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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

        st = new StringTokenizer(br.readLine());
		
        //음수 위치를 오름차순으로 정렬
        PriorityQueue<Integer> negativePQ = new PriorityQueue<>();
        //양수 위치를 내림차순으로 정렬
        PriorityQueue<Integer> positivePQ = new PriorityQueue<>(Collections.reverseOrder());

        for(int i=0;i<N;i++){
            int location = Integer.parseInt(st.nextToken());

            if(location < 0){
                negativePQ.add(location);
            }else{
                positivePQ.add(location);
            }
        }
		
        //음수/양수 위치의 가장 최대값 구하기
        int negativeMax = negativePQ.isEmpty() ? 0 : Math.abs(negativePQ.peek());
        int positiveMax = positivePQ.isEmpty() ? 0 : positivePQ.peek();
        
        int sum = 0;
        
        //다시 돌아오지 않아도 되는(가장 멀리 있는 책) 위치 구하기
        if(positiveMax > negativeMax){
            sum += positivePQ.peek();

            int count = M;

            while(count-- >0 && !positivePQ.isEmpty()){
                positivePQ.poll();
            }
        }else{
            sum += Math.abs(negativePQ.peek());

            int count = M;

            while(count-- >0 && !negativePQ.isEmpty()){
                negativePQ.poll();
            }
        }

        //음수 위치 처리
        while(!negativePQ.isEmpty()){
            sum += Math.abs(negativePQ.peek())*2;

            int count = M;

            while(count-- >0 && !negativePQ.isEmpty()){
                negativePQ.poll();
            }
        }

        //양수 위치 처리
        while(!positivePQ.isEmpty()){
            sum += positivePQ.peek()*2;

            int count = M;

            while(count-- >0 && !positivePQ.isEmpty()){
                positivePQ.poll();
            }
        }

        System.out.println(sum);
    }
}

 

 

실행 결과

---

 

 

팁

---

• 가장 이득이 되는건 멀리 가는걸 최대한 적게 하는 것이므로 멀리 가는걸 우선적으로 생각핸다.