도서관 (백준 1491) [JAVA]

 

문제

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

1461번: 도서관

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2초	128 MB	941	396	4170	42.338%

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

입력

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

출력

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

 

풀이

어차피 0에 도착하면 책을 다시 집으므로, 음수 양수를 따로 생각한다.

책을 쭉 정렬해놓은 다음에, 가장 먼곳에서부터 M개씩 들고 왔다갔다고 생각한다.

끝나는 곳이 0이 아니어도 되므로, 음수건 양수건 제일 먼 곳에 M개만큼 옮기고 끝내버리면 된다.

ArrayList에 하나는 양수, 하나는 음수로 넣은 뒤 양수는 내림차순, 음수는 오름차순으로 정렬한다 (이래야 절대값 제일 큰애가 맨 앞에)

리스트가 빌때까지 맨 앞에 애를 M개마다 뽑으면서 답에 *2해서 더해주고 (왔다가 돌아가므로)

음수 역시 절대값을 취해서 똑같이 해준 다음에

제일 멀리 있는 곳을 한번 빼주면 된다.

시간복잡도는 결국 원소의 개수 N개만큼만 반복하므로 $O(N)$ 이다.

 

코드

import java.util.ArrayList;
import java.util.Collections;
public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    public static void main(String[] args)throws Exception {
    	String[] str = br.readLine().split(" ");
    	int num;
    	int N = Integer.parseInt(str[0]);
    	int M = Integer.parseInt(str[1]);
    	
    	ArrayList<Integer> pos = new ArrayList<Integer>();
    	ArrayList<Integer> neg =  new ArrayList<Integer>(); 
    	
    	str = br.readLine().split(" ");
    	for(int i=0; i<N; i++) {
    		 num =  Integer.parseInt(str[i]);
    		 if(num > 0) pos.add(num);
    		 else neg.add(num);
    	}
    	System.out.println(steps(N,M,pos,neg));
    }

   public static long steps(int N, int M, ArrayList<Integer> pos, ArrayList<Integer> neg) {
	   long ans = 0;
	   int distance = 0;
	   int max = 0;
	   Collections.sort(pos, Collections.reverseOrder());
	   Collections.sort(neg);
	   while(!pos.isEmpty()) {
		   if(max < pos.get(0)) {
			   max = pos.get(0);
		   }
		   
		   for(int i=0; i<M; i++) {
			   
			   if(pos.isEmpty()) continue;
			   
			   if(i == 0) {
				   distance = pos.get(0);
				   ans = ans+distance*2;
			   } 
			   pos.remove(0);
		   }
	   }	   
	   while(!neg.isEmpty()) {
		   
		   if(max < Math.abs(neg.get(0))){
			   max = Math.abs(neg.get(0));
		   }
		   
		   for(int i=0; i<M; i++) {
			   if(neg.isEmpty()) continue;
			   if(i == 0) {
				   distance = neg.get(0);
				   ans = ans + Math.abs(distance)*2;
			   }
			   neg.remove(0);
		   }
	   }	   
	   ans = ans - max;
	   return ans;
   }
}

 

결과