[Java] 백준 1461 도서관

 

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

1461번: 도서관

---

1. 접근방법

 

첫번째 시도

음수 양수에서 가장 큰 수를 뽑아서 비교 후 작은수쪽을 첫번째 연산하고 가장큰수쪽을 마지막에 연산할때 마지막에 가장큰값을 한번만 더해주기

 

결과가 예상대로 나오지않음 (정상적으로 생각했는데 코드에 오류라고 생각함)

 

두번째 시도

음수 양수 각 배열을 만들고 각 배열별 총합을 구해 총합의 큰쪽은 나중에 연산하고 작은쪽을 먼저 해주고

마지막 연산 시 가장 큰값을 한번만 더해줌 

 

두번째시도에서도 결과가 예상대로 나오지 않았음 -> 합이 크다고 가장 큰건 아니였구나를 깨우침)

 

세번째 시도

음수 양수에서 가장 큰값만 하나씩 비교함 가장큰값을 저장해서 가지고있음

그리고 순서에상관없이 연산함 마지막에 가장큰값을 한번 빼주면되겠다.

-> 첫번째 시도와 비슷한대 뭔가 실수를 하고 못알아차려 세번시도하게 됐다.

 

2. 코드

 

import java.io.*;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
public class Main {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);
		byte read() {
			if (bufferPos == bufferState) {
				try {
					bufferState = dis.read(buffer, bufferPos = 0, bfs);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];
		}
		int nextInt() {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}
	static PriorityQueue<Integer> plus = new PriorityQueue<>(Collections.reverseOrder()), minus = new PriorityQueue<>(Collections.reverseOrder());
	static int n,m,res,pluscnt,minuscnt,plussum,minussum;
	public static void main(String[] args) {
		Reader in = new Reader();
		
		n = in.nextInt();
		m = in.nextInt();
		res =0;
		pluscnt = 0;
		minuscnt = 0;
		plussum = 0;
		minussum = 0;
		int temp;
		for(int i=0;i<n;i++) {
			temp = in.nextInt();
			if(temp>0) {
				plus.offer(temp);
				plussum+=temp;
				pluscnt++;
				
			}
			else {
				minus.offer(-temp);
				minussum += -temp;
				minuscnt++;
			}
		}
		if(minussum>plussum) {
			plus(0);
			minus(1);
		}else {
			minus(0);
			plus(1);
		}
		System.out.println(res);
	}
	private static void minus(int dir) {
		int book=0;
		int k=0;
		while(minuscnt>0) {
			book = minus.poll();
			minuscnt--;
			if(minuscnt>=1) {
			for(int i=0;i<m-1;i++) {
				minus.poll();
				minuscnt--;
				if(minuscnt==0) break;
			}
			}
			if(dir == 1 && k==0) res += book;
			else res += book*2;
			k++;
		}
	}
	private static void plus(int dir) {
		int book=0,k=0;;
		while(pluscnt>0) {
			book = plus.poll();
			pluscnt--;
			if(pluscnt>=1) {
				for(int i=0;i<m-1;i++) {
					plus.poll();
					pluscnt--;
					if(pluscnt==0) break;
				}
			}
			if(dir == 1 && k==0) res += book;
			else res += book*2;
			k++;
		}
	}
}

 

3.개선코드

 

 

import java.io.*;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
public class boj1461 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferPos = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);
		byte read() {
			if (bufferPos == bufferState) {
				try {
					bufferState = dis.read(buffer, bufferPos = 0, bfs);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPos++];
		}
		int nextInt() {
			int rtn = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do
				rtn = rtn * 10 + c - '0';
			while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -rtn;
			return rtn;
		}
	}
	static PriorityQueue<Integer> plus = new PriorityQueue<>(Collections.reverseOrder()), minus = new PriorityQueue<>(Collections.reverseOrder());
	static int n,m,res,pluscnt,minuscnt,plussum,minussum;
	public static void main(String[] args) {
		Reader in = new Reader();
		n = in.nextInt();
		m = in.nextInt();
		res =0;
		pluscnt = 0;
		minuscnt = 0;
		plussum = 0;
		minussum = 0;
		int temp;
		for(int i=0;i<n;i++) {
			temp = in.nextInt();
			if(temp>0) {
				plus.offer(temp);
				pluscnt++;
				
			}
			else {
				minus.offer(-temp);
				minuscnt++;
			}
		}
		int a=0,b=0,max=0;
		if(!plus.isEmpty()) {
			a= plus.peek();
			plus();
		}
		if(!minus.isEmpty()) {
			b= minus.peek();
			minus();
		}
		max = Math.max(a, b);
			
		System.out.println(res-max);
	}
	private static void minus() {
		int book=0;
		while(minuscnt>0) {
			book = minus.poll();
			minuscnt--;
			if(minuscnt>=1) {
				for(int i=0;i<m-1;i++) {
					minus.poll();
					minuscnt--;
					if(minuscnt==0) break;
				}
			}
			res += book*2;
		}
	}
	private static void plus() {
		int book=0;
		while(pluscnt>0) {
			book = plus.poll();
			pluscnt--;
			if(pluscnt>=1) {
				for(int i=0;i<m-1;i++) {
					plus.poll();
					pluscnt--;
					if(pluscnt==0) break;
				}
			}
			res += book*2;
		}
	}
}

 

느낀점 빠른입출력은 사기다.