백준 [자바 java] 1461 : 도서관

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

1461번: 도서관

사실 한번에 통과하긴 했지만 4번은 갈아엎었던 것 같다.

처음에는 그냥 음수, 양수 나누어서 가장 끝에서부터 차례로 한번에 들을 수 있는 책 만큼 건너뛰면서 세면 되지 않을까라고 생각했지만 다시 0으로 돌아오지 않아도 된다는 조건 때문에 실패했다.

그리고 받는 수를 다 우선순위큐에 넣어서 차례로 빼려고 했지만 그렇게 하면 양수부분에서는 절댓값이 작은 부분부터 탐색해서 옳은 답이 나오지 않는다. 

최종적으로 지금 한 대로 양수는 양수대로 음수는 음수대로 절댓값이 큰 순서대로 탐색하고 두 값들을 우선순위큐(내림)으로 처리했지만, 모든 수가 양수, 음수인 경우는 고려하지 않아 테케에 통과하지 못했었다.

 

앞으로 주의할 점 : 두 과정으로 나누는 방식을 사용했을 때 하나의 과정만 사용해야 하는 경우 꼭 고려하기

 

풀이코드

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


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());

        st = new StringTokenizer(br.readLine());


        PriorityQueue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder());

        int[] arr = new int[n];

        for(int i =0;i<n;i++) {
            int k = Integer.parseInt(st.nextToken());
            arr[i] = k;
        }

        Arrays.sort(arr);

        int ans = 0;

        int now = 0;

        while(true){
            if(arr[0] > 0) break;
            //System.out.println(arr[now]);
            q2.offer(Math.abs(arr[now]));
            now += m;
            if(now >= n || arr[now] >= 0) break;
        }

        now = n-1;



        while(true){
            if(arr[n-1] < 0) break;
            //System.out.println(arr[now]);
            q2.offer(Math.abs(arr[now]));
            now -= m;
            if(now < 0 || arr[now] < 0) break;
        }

        if(q2.isEmpty() != true) ans += q2.poll();

        while(q2.isEmpty() != true){
            ans += (q2.poll())*2;
        }

        System.out.println(ans);

    }
}