백준2014(소수의 곱)

jh Seo·2023년 3월 12일
백준우선순위 큐한번에 못 푼 문제
0

백준

목록 보기
138/194
post-custom-banner

개요

백준 2014번 : 소수의 곱

  • 입력
    첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

  • 출력
    첫째 줄에 문제에서 설명한 대로 소수의 곱을 나열했을 때, N번째 오는 것을 출력한다.

접근 방식

첫번째 방식

  1. 처음에 모든 소수값을 set과 우선순위 큐에 넣고
    우선순위 큐의 top값에 곱을 하며 계속
    set에 집어넣으며 N번째 set값을 출력하는 방식으로 진행했다.

  2. 하지만 몰랐던 부분은 모든 곱을 set에 집어넣는 부분이다.
    마지막 소수값을 곱하는 것보다 초반 소수값을 한번 더 곱하는 게
    더 이득이라고 생각이 들었다.

    따라서 처음 소수값만 여러개 곱해서 만든 수와
    마지막 소수값을 한번씩 곱해 만든 수를 비교했을 때의
    결과가 예상이 안 돼서 결국 검색을 하였다.

  3. 검색을 해본 결과 브루트 포스 방식으로 모든 수를 계산해서
    우선순위 큐에 집어넣는 방식이였고,
    간략히 서술하면 대충 N개의 priority_queue의 top값에
    K개의 소수를 다 곱한 후, 다시 큐에 넣는 느낌이였다.

  4. priority_queue와 초기 소수값을 받을 벡터를
    생성해줬다.

    //우선순위 큐
priority_queue<int, vector<int>, greater<int>> pq;
//초기 k개의 소수들 
vector<int> initialPrimeNums;
//N개의 pop한 숫자들
set<int> popped;

    pq에 모든 곱들을 넣고, initialPrimeNums에 초기 소수값들을 넣어준 후, popped엔 pq의 top값을 insert해 중복체크용으로 사용했다.

  5. 처음 구현은 2중 for문을 이용하여, 

    void Solution() {
	for (int i = 0; i < N; i++) {
			long long top = pq.top();
			for (int j = 0; j < K; j++) {
				//top값이 이미 뽑은 값중에 있다면 이미 계산했던 값이므로 break;
				if (popped.find(top) != popped.end()) break;
				//값을 곱했을때 int 범위 넘어갈시 continue;
				else if (top * initialPrimeNums[j] >= MAXINT) continue;
				//위의 조건들 넘어갔다면 pq에 푸시해줌
				pq.push(top * initialPrimeNums[j]);
			}
           //k개의 소수를 곱하고 넣는 연산이 끝났다면 popped에 insert
			popped.insert(top);
			//K개의 소수를 pq의 top에 곱한후 pq에 넣는 연산을 다 끝냈을 때, 비로소 pop
			pq.pop();
	}
	int cnt = 0;
	for (auto iter = popped.begin(); iter != popped.end(); ++iter)
	{
		if (cnt == N - 1) {
			cout << *iter;
			return;
		}
		cnt++;
	}
	
}

    이런식으로 pq.top()값에 K개의 소수를 곱한 후 pq에 도로 넣어주고 top값은 popped에 넣고 pop하는 과정을 N번 진행했다.
    그 후, popped에 N-1번째 값을 출력하려 했으나 틀렸습니다가 떴다.
    그 이유는 중복이 set에 의해 제거가 되고, int값을 넘어가는 범위도 제거가 되어서 popped의 사이즈가 N-1보다 작아서 발생했다.

  6. 위 문제를 해결하기 위해서, 

    for (int i = 0; i < N; i++) {
	//set이라 중복값 알아서 제거되므로 popped의 사이즈 N 맞추기 위해 N개 푸시해줌
	popped.insert(pq.top());
	pq.pop();
}

    임시방편으로 popped의 N-1번째 원소 출력 전에
    pq에서 N개의 원소를 popped에 넣어 줬는데 또 틀렸습니다가 떴다.
    문제는 중복제거 및 pq에서 pop을 이미 많이 해놔서
    pq의 사이즈가 N이 안되는 경우가 생기기 때문이였다.

  7. 당황해서 코드를 엎어버리고 다시 생각해봤다.
    pq와 popped의 사이즈로 반복문을 돌리지말고,
    무한루프를 통해 pq에 소수를 넣어주는 과정을
    반복하다가 popped의 사이즈가 N이 되었을 때, 답을 출력하도록 다시 짰다. 

    void Solution() {
	while(1){
		//우선순위 큐에서 제일 작은값
		long long top = pq.top();
		for (int j = 0; j < K; j++) {
			//top값이 이미 뽑은 값중에 있다면 이미 계산했던 값이므로 continue
			if (popped.find(top) != popped.end()) break;
			//값을 곱했을때 int 범위 넘어갈시 continue;
			else if (top * initialPrimeNums[j] >= MAXINT) continue;
			//위의 조건들 넘어갔다면 pq에 푸시해줌
			pq.push(top * initialPrimeNums[j]);
		}
		popped.insert(top);
		//insert연산 아끼려고 size비교를 insert위에 넣었었는데 생각해보니 
		//사이즈가 N-1일때, 들어온 값이 set안에 있다면 해당값이 답이 될수없으므로 insert밑에 넣어야함
		if (popped.size() == N) {
			cout << top;
			return;
		}
		//K개의 소수를 pq의 top에 곱한후 pq에 넣는 연산을 다 끝냈을 때, 비로소 pop
		pq.pop();
	}

}

    여기서도 문제가 생겼었다.
    popped.insert()연산을 한번 아끼려고
    괜히 if(popped.size()==N)부분을 insert 위로 올려서
    size==N-1일때 top출력으로 적었더니 당연히 틀렸습니다가 떴다.

    이유는 popped가 set이라 insert한다고 다 들어가는게 아니라
    중복일 경우 걸러버린다.
    따라서 insert위에 출력을 적어버리면 해당 출력값이 중복인지도 체크안한채 답으로 출력해버리는 꼴이라 틀렸습니다가 뜬다.

두번째 방식(더 효율적)

  1. 이 방식은 검색하다가 고수님의 글을 본건데,
    https://github.com/kks227/BOJ/blob/master/2000/2014.cpp
    모든 원소를 다 set에 넣어서 set의 N번째 원소를 찾을 필요없이
    중복검사하는 방식을 효율적으로 변경한 풀이이다.

    void Solution() {
	//이전값 저장용 변수
	int prev = -1;

	//N-1번째 순서의 수를 제거하는 과정
	for (int i = 0; i < N-1; i++) {
		//top값을 cur에 저장
		int cur = pq.top();
		//pop해줌
		pq.pop();
		//K개의 소수를 cur값에 곱해준 후 범위 안 넘어가면 pq에 넣어줌
		for (int j = 0; j < K; j++) {
			long long tmp = 1LL * cur * initialPrimeNums[j];
			if (tmp >= MAXINT) continue;
			pq.push(tmp);
		}
		//prev변수에 pop해준 top넣어놓고 
		prev = cur;
		//pop해준 값과 같은 수들 전부 제거 
		while (prev == pq.top()) pq.pop();
	}
	//위의 과정 끝나면 N번째 원소 남음 바로 출력
	cout << pq.top();
}

  2. 기본적으로 값을 greater<int> 방식의 priority_queue에 넣을 때,
    정렬되어 있으므로 top에 제일 작은 값이 들어있다.
    따라서 K개의 소수를 넣고 top값을 빼기전에 cur변수에 저장을 해둔다.

    	//이전값 저장용 변수
	int prev = -1;

	//N-1번째 순서의 수를 제거하는 과정
	for (int i = 0; i < N-1; i++) {
		//top값을 cur에 저장
		int cur = pq.top();
		//pop해줌
		pq.pop();

  3. pop연산 후, pq.top()에 해당하는 수와 prev값이 같은지 판단하는 식으로 제일 작은 값의 중복을 검사하는 방식이다. 

    		//K개의 소수를 cur값에 곱해준 후 범위 안 넘어가면 pq에 넣어줌
			for (int j = 0; j < K; j++) {
				long long tmp = 1LL * cur * initialPrimeNums[j];
				if (tmp >= MAXINT) continue;
				pq.push(tmp);
			}
			//prev변수에 pop해준 top넣어놓고 
			prev = cur;
			//pop해준 값과 같은 수들 전부 제거 
			while (prev == pq.top()) pq.pop();
		}

  4. 위의 pop 연산을 N-1번 반복을 통해 진행한다.
    반복문이 끝난 후 priority_queue의 top에 N번째 원소가
    존재하므로 해당 top이 답이다.

    	//위의 과정 끝나면 N번째 원소 남음 바로 출력
	cout << pq.top();

  5. 처음에 이방식을 보고 이해가 안 되었던 점은
    제일 작은 원소값만 중복여부를 검사하기때문에
    나머지 값들의 중복 여부는 왜 검사를 안하냐 였다.

    생각해보니 N-1번 pop 반복을 통해 어차피 제일작은값에 답이 들어있는 구조이므로 나머지 값들이 중복되어 있는지는 상관이 없다.

전체코드

첫번째 방식

#include<iostream>
#include<queue>
#include<set>
using namespace std;

//우선순위 큐
priority_queue<int, vector<int>, greater<int>> pq;
//초기 k개의 소수들 
vector<int> initialPrimeNums;
//N개의 pop한 숫자들
set<int> popped;

const int MAXINT = 2147483647;
int N, K;

void Input() {
	int tmp=0;
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> tmp;
		//처음에 들어온 값 소수 벡터에 넣어주고
		initialPrimeNums.push_back(tmp);
		//우선순위큐에도 넣어줌
		pq.push(tmp);
	}
}

//K개의 소수를 top에 곱해서 넣고 pop하는과정은 N번 넘게 해야함!
// 왜냐면 중복이 많아서 대체로 pq의 사이즈가 N개가 안되는 경우가 많음 
//따라서 무한루프로 구현해야함

void Solution() {
	while(1){
		//우선순위 큐에서 제일 작은값
		long long top = pq.top();
		for (int j = 0; j < K; j++) {
			//top값이 이미 뽑은 값중에 있다면 이미 계산했던 값이므로 continue
			if (popped.find(top) != popped.end()) break;
			//값을 곱했을때 int 범위 넘어갈시 continue;
			else if (top * initialPrimeNums[j] >= MAXINT) continue;
			//위의 조건들 넘어갔다면 pq에 푸시해줌
			pq.push(top * initialPrimeNums[j]);
		}
		//top값 insert
		popped.insert(top);
		//insert연산 아끼려고 size비교를 insert위에 넣었었는데 생각해보니 
		//사이즈가 N-1일때, 들어온 값이 set안에 있다면 해당값이 답이 될수없으므로 insert밑에 넣어야함
		if (popped.size() == N) {
			cout << top;
			return;
		}
		//K개의 소수를 pq의 top에 곱한후 pq에 넣는 연산을 다 끝냈을 때, 비로소 pop
		pq.pop();
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	Solution();
}

두번째 방식

#include<iostream>
#include<queue>
using namespace std;

//우선순위 큐
priority_queue<int, vector<int>, greater<int>> pq;
//초기 k개의 소수들 
vector<int> initialPrimeNums;

const int MAXINT = 2147483647;
int N, K;

void Input() {
	int tmp=0;
	cin >> K >> N;
	for (int i = 0; i < K; i++) {
		cin >> tmp;
		//처음에 들어온 값 소수 벡터에 넣어주고
		initialPrimeNums.push_back(tmp);
		//우선순위큐에도 넣어줌
		pq.push(tmp);
	}
}

void Solution() {
	//이전값 저장용 변수
	int prev = -1;
	//N-1번째 순서의 수를 제거하는 과정
	for (int i = 0; i < N-1; i++) {
		//top값을 cur에 저장
		int cur = pq.top();
		//pop해줌
		pq.pop();
		//K개의 소수를 cur값에 곱해준 후 범위 안 넘어가면 pq에 넣어줌
		for (int j = 0; j < K; j++) {
			long long tmp = 1LL * cur * initialPrimeNums[j];
			if (tmp >= MAXINT) continue;
			pq.push(tmp);
		}
		//prev변수에 pop해준 top넣어놓고 
		prev = cur;
		//pop해준 값과 같은 수들 전부 제거 
		while (prev == pq.top()) pq.pop();
	}
	//위의 과정 끝나면 N번째 원소 남음 바로 출력
	cout << pq.top();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
	Solution();
}

문풀후생

일단 K개의 소수를 top값에 다 곱해준후 다시 넣어주는 과정이 흥미로웠고 다양한 반례를 통해 많이 고친 코드라서
실력향상에 도움이 되는 문제였던 것 같다.

또한 2^31의 값을 비교할때 난 MAXINT값으로 미리 2^31-1값을 잡아서 했지만 저 깃허브링크의 코드작성자분은 1LL<<31 이런식으로
비트를 통해 구현하셨다.

레퍼런스

https://github.com/kks227/BOJ/blob/master/2000/2014.cpp

profile
jh Seo
코딩 창고!
이전 포스트

백준2075(N번째 큰 수)

다음 포스트

백준2696번(중앙값 구하기)

post-custom-banner

0개의 댓글