글 읽기 - Java 우선순위 큐를 이용하면 왜 시간초과가 나는건가요?

rkarud1234 2년 전 0

다른 자바 코드들 참고해봤는데

우선순위 큐로 구현한 부분을 배열로 구현한 것 말고는 큰 차이가 없다고 생각되는데

시간초과가 나옵니다.

단순히 while문이 돌아가는 곳만 시간을 계산해봐도 최대N*N*2라고 계산되는데,,,

제가 놓치고 있는 부분이나 잘못 생각하고 있는 부분이 있다면 지적 부탁드리겠습니다 감사합니다,,

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 입력부
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][4];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// 오름차순
		PriorityQueue<Integer> ab = new PriorityQueue<Integer>();
		// 내림차순
		PriorityQueue<Integer> cd = new PriorityQueue<Integer>(Collections.reverseOrder());

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// a랑 b의 합
				ab.add(arr[i][0] + arr[j][1]);
				// c랑 d의 합
				cd.add(arr[i][2] + arr[j][3]);
			}
		}

		long cnt = 0;
		while (!ab.isEmpty() && !cd.isEmpty()) {
			int sum = ab.peek() + cd.peek();
			if (sum == 0) { // 정답을 찾았을 경우
				long abcnt = 1;
				long cdcnt = 1;
				// 중복된 값이 없을때까지 탐색
				while (!ab.isEmpty() && ab.poll() == ab.peek())
					abcnt++;
				while (!cd.isEmpty() && cd.poll() == cd.peek())
					cdcnt++;
				cnt += (abcnt * cdcnt);
			} else if (sum > 0) { // 0보다 클 경우 cd값을 줄인다
				cd.poll();
			} else { // 0보다 작을 경우 ab값을 높인다
				ab.poll();
			}
		}
		System.out.println(cnt);
	}
}

djm03178 2년 전 1

우선순위 큐에서 원소를 하나 추가하거나 제거하는 것의 시간 복잡도는 O(logN)입니다. 따라서 O(N^2)개의 원소를 모두 add하고 poll 하는 데에는 O(N^2logN) 시간이 걸립니다.

현재 의도된 시간 복잡도 역시 O(N^2logN)이기는 하나, 시간 자체가 넉넉한 문제가 아니기 때문에 상수가 크면 통과하기 어려울 수 있습니다. 정렬에 비해서는 훨씬 느린 방법이라고 생각합니다.

rkarud1234 2년 전 0

아.. 데이터의 삽입/삭제가 일어날 때마다 힙 내부에서도 정렬이 일어난다는 사실을 간과하고 단순히 우선순위 큐가 배열을 정렬하는 것보다 빠를 거라고 생각해버렸네요ㅠ

답변 감사합니다!!

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

문제

문제

출처

ICPC

Java 우선순위 큐를 이용하면 왜 시간초과가 나는건가요?

rkarud1234 2년 전 0

djm03178 2년 전 1

rkarud1234 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말