글 읽기 - 시간초과 도와주세요 ㅠㅠㅠ

sik8856 4년 전 0

우선순위 큐를 사용해서 제일 작은 값을 pop해주는 방법으로 풀었는데

왜 계속 시간초과가 나는걸까요...?

도와주세요 ㅠㅠㅠㅠ

package wewe;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.HashMap;
	import java.util.Map;
	import java.util.Scanner;
	import java.util.StringTokenizer;
	
	public class homework {
	
		public static void main(String[] args) {
			
			//sc.init();
			Scanner scanner = new Scanner(System.in);
	
			int n = scanner.nextInt();
			int k = scanner.nextInt();
			prQ pre = new prQ(k*n);
			int count =0;
			Map <Integer,Long> map = new HashMap<Integer,Long>();
			long[] ans = new long[k];
			
			for (int i = 0; i < n; i++) {
				int c = scanner.nextInt();
				ans[i] = c;
				push(pre, c);
				map.put(count, (long) c);
				count++;
			}
			
			long head = 0;
			
			for(int j=0; j < k; j++) {
				head = pop(pre);
			
				for(int i=0; i < n;i++) {
					long value = head * ans[i];
		
					if(!map.containsValue(value)) {
						map.put(count, value);
						count++;
						push(pre,value);
			
					}
					
				}
				
				
				}
		
			System.out.println(head);
		}
	
		static class prQ implements Cloneable {
			prQ(int k) {
				this.count = 0;
				this.k = k;
				arr = new long[k];
			}
	
			public Object clone() {
				Object obj = null;
				try {
					obj = super.clone();
				} catch (Exception e) {
				}
				return obj;
			}
	
			public int k;
			public int count;
			public long[] arr;
	
		}
	
		static void push(prQ pr, long data) {
			if (pr.count > 100000) {
				return;
			}
			pr.arr[pr.count] = data;
	
			int now = pr.count;
			int parent = (now - 1) / 2;
	
			while (now > 0 && pr.arr[now] < pr.arr[parent]) {
				long temp = pr.arr[now];
				pr.arr[now] = pr.arr[parent];
				pr.arr[parent] = temp;
				now = parent;
				parent = (parent - 1) / 2;
			}
			pr.count++;
		}
	
		static long pop(prQ pr) {
			long res = pr.arr[0];
			pr.count--;
			pr.arr[0] = pr.arr[pr.count];
			int now = 0;
			int leftChild = 1;
			int rightChild = 2;
			int target = now;
			while (leftChild < pr.count) {
				if (pr.arr[leftChild] < pr.arr[target]) {
					target = leftChild;
				}
				if (pr.arr[rightChild] < pr.arr[target] && rightChild < pr.count) {
					target = rightChild;
				}
				if (now == target) {
					break;
				} else {
					long temp = pr.arr[now];
					pr.arr[now] = pr.arr[target];
					pr.arr[target] = temp;
	
					now = target;
					leftChild = now * 2 + 1;
					rightChild = now * 2 + 2;
				}
			}
	
			return res;
	
		}
		
		
	}

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

문제

문제

출처

ICPC

시간초과 도와주세요 ㅠㅠㅠ

sik8856 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말