글 읽기 - 2014번 시간 초과 질문드립니다.

mygumi 7년 전 0

큐에서 맨 앞 요소를 하나씩 빼서 주어진 소수를 각각 곱하면서 다시 큐에 넣는 방식으로 구현했습니다.

제 생각으로는 K도 100개밖에 안되고 시간은 충분할꺼 같은데...

8%에서 시간초과가 뜨네요......

어디서 무한루프가 돌고 있는건지.....?

도저히 찾을 수가 없네요.

고수님들 도와주세요 ㅠㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	private void solve() {
		int k = sc.nextInt();
		int n = sc.nextInt();
		
		// 소수 리스트, 소수와 비교하여 곱한 값 넣는 큐, 최종 리스트  
		// 큐의 맨 앞 요소를 빼서 각 소수를 곱하면서 큐에 다시 넣을 것이다.
		
		int[] prime = new int[k];
		PriorityQueue<Integer> q_pop = new PriorityQueue<>();
		
		for(int i=0;i<k;i++) {
			prime[i] = sc.nextInt();
			q_pop.add(prime[i]);
		}
		
		int pop = 0;
		
		for(int i=0;i<n;i++) {
			// n번째 뺀 값이 n번째 수가 된다.
			int top = q_pop.peek();
			
			// 큐를 활용하여 삽입마다 오름차순으로 정렬됨으로써 원하는 값들을 리스트에 저장 가능.
			for(int j=0;j<k;j++) {
				int value = top * prime[j];
				if (value > 1) {
					q_pop.add(value);
				}
			}
			
			while(pop == q_pop.peek()) {
				q_pop.poll();
			}
			
			pop = q_pop.poll();
			
		}
		System.out.println(pop);
	}
	
	public static void main(String[] args) {
		sc.init();

		new Main().solve();
	}

	static class sc {
		private static BufferedReader br;
		private static StringTokenizer st;

		static void init() {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		static String readLine() {
			try {
				return br.readLine();
			} catch (IOException e) {
			}

			return null;
		}

		static String readLineReplace() {
			try {
				return br.readLine().replaceAll("\\s+", "");
			} catch (IOException e) {
			}

			return null;
		}

		static String next() {
			while (!st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			}

			return st.nextToken();
		}

		static int nextInt() {
			return Integer.parseInt(next());
		}

		static double nextDouble() {
			return Double.parseDouble(next());
		}
	}

}

dlwodnsdl 7년 전 1

약수가 여러개인 수가 큐에 여러번 들어가 있어서 속도를 느리게 만듭니다. 큐에서 꺼낼때 중복체크를 하지마시고 큐에 넣기 전에 중복체크를 하시는게 좋습니다.

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

문제

문제

출처

ICPC

2014번 시간 초과 질문드립니다.

mygumi 7년 전 0

dlwodnsdl 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말