글 읽기 - 시간초과를 어떻게 해결해야할지 모르겠습니다..

pjy1368 4년 전 0

문제에서 요구하는 대로 우선순위큐 2개를 이용해서 삽입과 삭제의 과정을 수행하였는데, 1%에서 시간초과가 났습니다.

여기서 어떻게 접근해야 시간을 줄일 수 있을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder()); // 내림차순
			PriorityQueue<Integer> minPq = new PriorityQueue<>(); // 오름차순

			int N = Integer.parseInt(br.readLine());
			while (N-- > 0) {
				st = new StringTokenizer(br.readLine());
				String command = st.nextToken();
				int val = Integer.parseInt(st.nextToken());

				if (command.equals("I")) {
					maxPq.offer(val);
					minPq.offer(val);
				} else {
					if (val == 1) { // 최댓값 제거
						if (maxPq.isEmpty()) {
							continue;
						}
						int max = maxPq.peek();
						maxPq.remove(max);
						minPq.remove(max);
					} else { // 최솟값 제거
						if (minPq.isEmpty()) {
							continue;
						}
						int min = minPq.peek();
						maxPq.remove(min);
						minPq.remove(min);
					}
				}
			}

			if (maxPq.isEmpty() || minPq.isEmpty()) {
				bw.write("EMPTY\n");
			} else {
				bw.write((maxPq.poll()) + " " + (minPq.poll()) + "\n");
			}
		}

		bw.flush();
		bw.close();
		br.close();
	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과를 어떻게 해결해야할지 모르겠습니다..

pjy1368 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말