[Java] 백준 2014번 : 소수의 곱*

1. 문제

https://www.acmicpc.net/problem/2014

2014번: 소수의 곱

 

 

 

2. 풀이과정

기본적으로, 주어진 소수들을 계속 곱하면서, PriorityQueue에 넣는다. 여기서 중복 값을 제외시키는 방식으로 N번째 수를 찾았다. 중복된 값을 제외시키는 방식을 처음엔 contain으로 검사해서 시간초과가 발생했다. 질문 검색으로 힌트를 보고, 2*5*7 = 2*7*5 = 5*2*7 = 5*7*2 = 7*2*5 = 7*5*2와 같이 같은 값이 곱하는 순서만 바뀌어 계속 들어가는 것이 원인이였다.

 

따라서 입력된 순서 반대로만 곱해가도록 하였다. 현재 보고 있는 수에 자신이 곱해져있으면, 그 뒤에 값은 곱하지 못하게 break를 한다.

 

실행 과정을 살펴보면, 맨 마지막 수가 자신보다 작거나 같은 수만 오도록 되어있다.

step1) 
2, 5, 7

step2) 
2x2
5x2, 5x5
7x2, 7x5, 7x7

step3)
2x2x2
5x2x2, 5x5x2, 5x5x5
7x2x2, 7x5x2, 7x5x5, 7x7x2, 7x7x5, 7x7x7

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());//k개의 수
		int N = Integer.parseInt(st.nextToken());//n번째
		
		long prime[] = new long[K];
		PriorityQueue<Long> pq = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<K; i++) {
			prime[i] = Long.parseLong(st.nextToken());
			pq.offer(prime[i]);
		}
		
		for(int i=0; i<N-1; i++) {//N번째 수를 찾을 때까지 반복
			long n = pq.poll();
			for(int j=0; j<K; j++) {//기존의 수에서 주어진 소수들을 곱함
				long temp = n*prime[j];
				if(temp >= (long)2<<30) {//답은 2^30보다 작다
					break;
				}
				pq.offer(temp);
				if(n%prime[j]==0) {//순서대로 곱해진 것만 받겠다.
					break;
				}
			}
		}
		System.out.println(pq.poll());
	}
}

 

 

 

 

위의 방식이 우선 다 PriorityQueue에 넣고 최솟값을 찾는 방식이라면, 아래는 최솟값이 아니면, 지금 보지말자는 방식이다. 위의 경우 큰 값도 미리 들어가서 PriorityQueue에 담는 값이 커지고 그만큼 연산도 증가한다. 따라서 아래 코드일 경우 시간복잡도 측면에서 좋은 코드같다.

 

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int K = Integer.parseInt(st.nextToken());//k개의 수
		int N = Integer.parseInt(st.nextToken());//n번째
		
		int prime[] = new int[K];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<K; i++) {
			prime[i] = Integer.parseInt(st.nextToken());
		}
		
		int result[] = new int[200000];
		int p[] = new int[K];
		result[0] = 1;
		for(int i=1; i<=N; ) {
			int min = Integer.MAX_VALUE;
			int minIdx = 0;
			for(int j=0; j<K; j++) {
				int temp = result[p[j]]*prime[j];//기존의 수에서 소수를 곱함
				if(temp < min) {
					min = temp;
					minIdx = j;
				}
			}
			if(result[i-1]!=min) {
				result[i++] = min;
			}
			//해당 소수를 곱한 최소값을 썼으니 다음으로 옮김
			p[minIdx]++; 
		}
		System.out.println(result[N]);
	}
}