백준 2014번 소수의 곱

www.acmicpc.net/problem/2014

2014번: 소수의 곱

 

12번 푸러따,,,,,,, 의지의 한국인이라는 걸 보여줘버려따,,,,,,,,

문제를 처음 접했을 때는 어떻게 풀어야할지 감도 안오고 우선순위큐로 뭐 어쩌라는건지,,, 싶어서 다른 문제 풀었는데, 머리를 감다가 번득 생각났다. 우선순위에서 제일 작은 값을 꺼내고, 소수들과 곱해서 다시 집어넣으면 되겠구나!

그래도 시행착오를 많이 겪었다. 

크게 세번의 과정을 거쳐 풀 수 있었다. 

 

❌실패코드 1

#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include<queue>
using namespace std;

priority_queue<long long, vector<long long>, greater<long long>> pq;
long long arr[100];

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &arr[i]);
		pq.push(arr[i]);
	}
	int cnt = 0;
	long long prev = 1;
	while (cnt < k) {
		long long num = pq.top();
		//printf("%d\n", num);
		pq.pop();
		if (prev == num) continue;
		cnt++;
		if (cnt == k) {
			printf("%lld", num);
		}
		else {
			for (int i = 0; i < n; i++) {
				pq.push(num * arr[i]);
			}
		}
		prev = num;
	}
}

처음 입력받은 소수만 담겨져있는 배열을 따로 만든 후, 모두 우선순위 큐 pq에 push해준다.

pop한 수에 대해서 소수배열에 있는 모든 값들과 다 곱한 후, 다시 큐에 집어넣어준다. 

이렇게만 구성하면 중복이라는 문제점이 생긴다. 

pop된 2를 3에 곱한 후 넣는 것과 , pop된 3에 2를 곱하고 넣는 것이 같기때문이다. 

그래서 prev라는 변수를 만들어 이전에 나온 값을 저장해두고, 새롭게 pop한 값과 비교해 같으면 넘어가고

다르면 카운팅을 해주었다.

결과는 ❌메모리초과❌

왜 메모리초과가 나는 걸까? 중복된 수들이 모두 우선순위 큐에 들어가기 때문에 메모리가 터지는 것 같다.

 이 문제점을 보완해서 코드를 다시 짜봤다. 

 

❌실패코드 2

#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
unordered_map<long, bool> visited ;
int arr[100];

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		pq.push(arr[i]);
		visited[arr[i]] = true;
	}
	int cnt = 0;
	while (cnt < k) {
		int num = pq.top();
		//printf("%d\n", num);
		pq.pop();
		cnt++;
		if (cnt == k) printf("%ld", num);
		else {
			for (int i = 0; i < n; i++) {
				long new_num = num * arr[i];
				if (!visited[new_num] && new_num < pow(2, 31)) {
					pq.push(new_num);
					visited[new_num] = true;
				}
			}
		}
	}
}

map을 이용하여 방문처리를 해 중복임을 확인해주었다. 

방문처리가 안된 수라면 pq에 넣어준 후, 방문처리를 해준다. 

pop된 숫자에 소수들을 곱한 수가 방문처리 된 숫자라면 그냥 넘겨버렸다.

결과는 ❌메모리초과❌

중복된 수를 제거해줬는데 왜 또 메모리초과가 나는 걸까? 아무리 생각해봐도 모르겠어서 다른 사람들의 글을 참고했다.

내가 필요한 수보다 더 많은 수를 집어넣기 때문인 거 같다. 

예를 들어 내가 찾는 수가 6번째 수이고 현재 소수가 [2,3,5,7] 이라면 큐 안에 6개만 들어가있게 만들어주면 된다. 

2를 pop한 후, 소수와 곱하면 4,6,10,14 라는 수가 새로 생긴다.

나는 6번째 수를 찾을거니까 큐에는 2 3 4 5 6 7 이라는 수만 있으면 된다. 즉 새로 만든 10,14는 필요하지 않다는 것

그렇기 때문에 현재 있는 수보다 크면서 사이즈를 초과한다면 굳이 큐에 넣어주지 않아도 되는 것이다. 

하지만 현재 가장 큰 수보다 작다면 큐의 사이즈가 늘어나더라도 넣어줘야한다. 최솟값인 소수들부터 뽑아내기때문이다. 

이 점을 보완해 다시 코드를 짜보았다. 

 

⭕성공코드 

#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
using namespace std;

priority_queue<long long, vector<long long >, greater<long long >> pq;
unordered_map<long long, bool> visited;
long long  arr[100];

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		pq.push(arr[i]);
		visited[arr[i]] = true;
	}
	long long nmax = arr[n - 1];
	int cnt = 0;
	while (1) {
		long long num = pq.top();
		pq.pop();
		cnt++;
		if (cnt == k) {
			printf("%lld", num);
			break;
		}

		for (int i = 0; i < n; i++) {
			long long  new_num = num * arr[i];
			if (pq.size() > k-cnt && new_num > nmax) continue;
			if (!visited[new_num] ) {
				pq.push(new_num);
				visited[new_num] = true;
				nmax = max(nmax, new_num);
			}
		}
	}
}

nmax라는 변수를 통해서 큐에 들어간 최댓값을 계속해서 업데이트 해준다. 

35번째 줄이 핵심이다.

현재 큐의 사이즈가 내가 필요한수 k - cnt 보다 크면서 새로 만든 수가 nmax보다 크다면 어차피 들어와도 그 전에 while문에서 탈출해버리기때문에 넣어줄 필요가 없는 수인거다. 

 

 

👀남의 코드 

내 코드는 92ms가 걸리는데 거의 4배 가량 차이나는,,,, 24ms코드가 있어서 공부해보았다 

#include <iostream>
#include <queue>
using namespace std;
typedef long long Long;

int K, N;
Long num[100];
priority_queue <Long, vector<Long>,greater<Long>> pq;

int main() {
	cin >> K >> N;
	for (int i = 0; i < K; i++)
	{
		cin >> num[i];
		pq.push(num[i]);
	}

	Long f = 0;

	for (int i = 0; i < N; i++)
	{
		f = pq.top();
		pq.pop();
		for (int j = 0; j < K; j++)
		{
			Long value = f * num[j];
			pq.push(value);
			if (f % num[j] == 0) {
				break;
			}
		}
	}
	cout << f;
	return 0;
}