(프로그래머스) 소수 찾기

문제 링크

• 프로그래머스

요약

• BP 할 때 값의 범위를 조심하자.

최종 §

결과

• 그냥 BFS-like 방식으로 찾았다.
  • 어떤 종이조각을 반영했는지를 7bit BMS로 추적하고, 나머지 25bit에는 현재 숫자를 BP 하는 방식을 사용했고
  • Queue에 넣을 때 BMS에서 반영이 안된 종이조각을 찾아 뒤에 붙여 넣는 방식이다.

#include <string>
#include <vector>
#include <queue>
#include <set>
 
using namespace std;
 
#define PACK(bms, num) (((bms) << 25) | ((num) & 0x1FFFFFF))
#define UNPACK_BMS(pack) (((pack) >> 25) & 0x7F)
#define UNPACK_NUM(pack) ((pack) & 0x1FFFFFF)
 
int solution(string numbers) {
	queue<int> q;
	set<int> proc_set, ret_set;
 
	for (int i = 0; i < numbers.size(); i++) {
		if (numbers[i] > '0') {
			q.push(PACK(1 << i, numbers[i] - '0'));
			proc_set.insert(numbers[i] - '0');
		}
	}
 
	while (!q.empty()) {
		int pack = q.front();
		int bms = UNPACK_BMS(pack);
		int num = UNPACK_NUM(pack);
 
		q.pop();
 
		if (num > 1) {
			bool is_target = true;
 
			for (int i = 2; i < num; i++) {
				if (num % i == 0) {
					is_target = false;
					break;
				}
			}
 
			if (is_target) {
				ret_set.insert(num);
			}
		}
 
		for (int i = 0; i < numbers.size(); i++) {
			if (!((bms >> i) & 0x1)) {
				int next = num * 10 + (numbers[i] - '0');
 
				if (proc_set.find(next) == proc_set.end()) {
					q.push(PACK(bms | (1 << i), next));
					proc_set.insert(next);
				}
			}
		}
	}
 
	return ret_set.size();
}

• 조심해야 할 것은:
  • BP 할 때 값의 범위를 잘 생각해야 된다: 무의식적으로 16+16bit를 사용했는데, 값의 크기가 최대 7자리이기 때문에 16bit로는 모자라다.
  • 반영된 종이만 BMS로 추적하면 중복된 숫자를 처리하게 된다: 중복된 숫자를 queue에 넣어도 timeout은 안나지만, 위 코드에서는 proc_set 으로 중복된 숫자가 queue에 들어가지 않도록 방지해놓았다.