[BOJ] 백준 [1461] 도서관 JAVA

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

1461번: 도서관

[문제]

[풀이]

정렬 , 그리디 문제이다.
책을 제자리에 놓기위해 그 만큼 전진을 해야하는데 , 최대 M권을 같이 들고갈수 있기 때문에
기준점으로부터 제일 멀리있는 지점을 고르면 m-1개는 가는길에 갖다 놓을 수 있기때문에 
우선 제일 멀리있는 지점을 찾아야 한다.

그러나 제일 마지막에 놓는 책은 다시 돌아올 필요가 없기 때문에 편도로 한번만 가고
나머지는 왕복처리하면 끝.

우선순위 큐를이용해서 양수면 내림차순
음수면 오름차순으로 해서 
절대값이 제일 높은 값이 맨 앞으로 오게 해서 서로 비교한 다음 , 큰 값을 고르고 
m-1 만큼 poll을 해주는것을 반복하면 된다. 

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
public class Main {
    static PriorityQueue<Integer> pq,nq;
    static ArrayList<Integer> book;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int n = input[0],m=input[1],cnt=0;
        pq = new PriorityQueue<>((o1, o2) -> o2-o1);
        nq = new PriorityQueue<>((o1, o2) -> o1-o2);
        Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed()
                .forEach(e->{ if(e>0) pq.add(e); else nq.add(e);});
 
        if(pq.isEmpty()){
            cnt+=nq.poll()*-1;
            for(int i=0;i<m-1;i++) nq.poll();
        }else if(nq.isEmpty()){
            cnt+=pq.poll();
            for(int i=0;i<m-1;i++) pq.poll();
        }
        else if(pq.peek() > nq.peek()*-1){
            cnt+=pq.poll();
            for(int i=0;i<m-1;i++) pq.poll();
        }else{
            cnt+=nq.poll()*-1;
            for(int i=0;i<m-1;i++) nq.poll();
        }
 
        while (!pq.isEmpty()){
            cnt+=pq.poll()*2;
            for(int i=0;i<m-1;i++) pq.poll();
        }
        while ( !nq.isEmpty()){
            cnt+=nq.poll()*-2;
            for(int i=0;i<m-1;i++) nq.poll();
        }
        System.out.println(cnt);
    }
 
 
 
 
}