[BOJ/JAVA] 백준 1781번 : 컵라면

1781번: 컵라면

---

 

• 생각

1. 먼저, 2차원 배열에 값들을 넣어준 뒤 2차원 배열 정렬을 deadline으로 한다. 같은 deadline들 중 가장 큰 컵라면의 수를 더 해준다. O(n)의 시간으로 계산할 수 있다. ==>> 문제는 n이 7이고 deadline이 1이 5개, 7이 2개이면 deadline 1중에서 1개를 고르고, 7에서 2개 모두 더해줄 수 있다. (결국, 정확하게 구할 수 없음)

 

2. 먼저, 2차원 배열을 2개 만든다. 1개 배열엔 입력한 값들이 들어가고 1개 배열엔 입력된 배열을 컵라면 수를 내림차순으로 정렬한다. 가장 큰 컵라면 수부터 배열을 채우는데 해당 데드라인에 값이 있으면 해당 데드라인-1에 더 작은 값을 넣는다.   ==>> 시간 초과

 

3. 찾아보니 우선순위 큐를 사용 많이하는 것 같았다.

 

• 코드

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.PriorityQueue;

public class Main {
	static int N;
	static int[][] array;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(FindMaxValue());
	}
	
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
		N = in.readInt();
		array = new int[N][2];
		
		for(int i = 0; i < N; i++) {
			array[i][0] = in.readInt();
			array[i][1] = in.readInt();
		}
		
		// 2차원 배열 정렬 (deadline 오름차순)
		Arrays.sort(array, new Comparator<int[]>() {
		    @Override
		    public int compare(int[] o1, int[] o2) {
		        return o1[0] - o2[0];
		    }
		});
	}
	
	private static int FindMaxValue() {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int sum = 0;
        for (int i = 0; i < N; i++) {
            queue.add(array[i][1]);
            while (!queue.isEmpty() && queue.size() > array[i][0]) 
            	queue.poll();
        }
        while (!queue.isEmpty())
            sum += queue.poll();
		return sum;
	}
	
    // Stream
	private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}