2014 : 소수의 곱 - JAVA

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

2014번: 소수의 곱

발상이 상당히 어려운 문제였다.

소수를 몇번 사용하는지에 대한 제약이 없어서 2를 10번 곱할수 있고, 2를 7번 곱하고 3을 9번 곱할수도 있기 때문이다.

소수를 같은수를 몇개든 사용해서 곱할수 있고, 이렇게 나온 수들을 오름차순하여 n번째 숫자를 출력하면 되는 문제이다.

처음엔 우선순위 큐를 왜 사용해야하는지 몰랐으나, 숫자를 하나 빼서 정렬하는 과정에서 가장 적절한 자료구조가 우선순위 큐 임을 생각했고 사용했다. 앞서 말했듯 같은 수를 몇번이든지 곱해도 상관없다.

만약, 입력값으로 소수가 2 5가 들어오면 아래와 같은 로직이 전개된다.

1. 우선순위 큐에 2, 5를 넣는다.

2. 우선순위 큐에서 2를 꺼내고, 2 x 2, 5 x 2를 한 값들을 우선순위 큐에 넣는다.

4, 5, 10 순서로 우선순위 큐가 짜여 있을 것이다.

3. 우선순위 큐에서 4을 꺼내고, 4 x 4, 5 x 4, 10 x 4를 한 값들을 우선순위 큐에 넣는다.

이러면 이제 5, 10, 16, 20, 40 순서대로 우선순위 큐가 짜여 있을 것이다.

4. 이런 시행을 총 n번 반복한다.

의 과정 중 중복된 수를 제거해나가면 된다. 하지만 나는 중복된 수를 제거해나가는 과정에서 방법이 잘못된것인지 계속 오답이 도출됐다.

중복된 수는 TreeSet을 사용했더니 메모리 초과가 떴고, 반복문을 하나 더 돌려서 pq.peek()값과 res가 같다면 그 값을  삭제시켜버리는 연산을 사용했는데도 메모리 초과가 떴다. 2^31보다 작은 수까지는 허용되니까, 어떤 경우에선 정말 많은 숫자가 우선순위 큐에 삽입 될수 있으니 메모리 초과가 뜬것 같다.

즉, 나는 제거 로직을 제대로 생각하지 않고 문제를 풀었다.

아래는 내가 작성한 메모리 초과 코드이다.

import java.io.*;
import java.util.*;
public class sol300 {
	static int k,n;
	static TreeSet<Integer> mul;
	static PriorityQueue<Integer> pq;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		k = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		int res=0;
		int[] arr = new int[k];
		mul = new TreeSet<>();
		pq = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < k; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			pq.add(arr[i]);
		}
		
		for(int g = 0; g < n; g++){
			res = pq.poll();
			for(int i = 0; i < k; i++) {
				if(res*arr[i] < (long)Math.pow(2, 31)) {
					pq.add(res*arr[i]);
				}
			}
			while(pq.peek() == res) {
				pq.remove();
			}
		}

		System.out.println(res);
	}
}

TreeSet을 사용한 방식보다 사용된 자료구조도 적은데 메모리 초과가 난 것이다.

여기서 -1로 바꿔보고 res를 사용하지 않아보고 자료형을 long으로 바꿔보고 pow 대신 비트 연산을 해보고 중복된걸 제대로 제거하지 않아서 메모리 초과가 발생한게 아닐까 하는 생각에 peek한 값과, 소수를 나눠서 0이 되는걸 삭제시켜봤다.

그래도 메모리초과가 떴다.

테스트 케이스 맞기까지 4시간 걸렸는데, 메모리 초과를 피하기 위해, 이외 적기도 민망할 수많은 헛짓을 했다.

 

결국 다시 중복된걸 제대로 제거하지 않아서 메모리 초과가 발생한게 아닐까 하는 생각에 peek한 값과, 소수를 나눠서 0이 될때 break를 걸어봤다.

 

정답이었다.

 

나는 바보같이 이미 메모리초과가 되게끔 만들어놓고 거기서 뺴는 과정을 수행했고, 그것을 알기까지 1시간이 넘는 시간이 걸렸다.

 

if(res%arr[i] == 0) {

break;

}

답에서 이 연산은

    2    5

2  4   10

5 10X  25

의 배열이 있을때 X친곳의 접근을 막아서 중복된것 삽입을 막는다는 의미다. 4를 기준으로 중복된 값들이 늘어져있는데, 중복된 값 삽입을 방지하기 위함이다. 

 

다음은 정답 코드이다.

 

import java.io.*;
import java.util.*;
public class sol300 {
	static int k,n;
	static int MAX = 2147483647;
	static PriorityQueue<Long> pq;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		k = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		long res=0;
		long[] arr = new long[k];
		pq = new PriorityQueue<>();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < k; i++) {
			arr[i] = Long.parseLong(st.nextToken());
			pq.add(arr[i]);
		}
		
		for(int g = 0; g < n; g++){
			res = pq.poll();
			
			for(int i = 0; i < k; i++) {
				if(res*arr[i] <= MAX) {
					pq.add(res*arr[i]);
					if(res%arr[i] == 0) {
						break;
					}
				}
			}

			
		}

		System.out.println(res);
	}
}

발상을 이상하게 하여 쓸데없이 1시간을 잡아먹었다.