자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는?

[eng][kor]

std::array가 std::map의 키로 쓰일수 있다는 것을 이번 문제를 풀며 처음 알게 되어 사용해 보았고, 문제는 다음처럼 풀었다.


1) 으로 무한히 큐브 수를 구해 나간다.

2) 1)에서 큐브 수를 구할 때마다, 이 수를 cubemap 에 업데이트 한다. cubemap은 digit을 키로 큐브수를 관리하는 맵이다. 예를 들어 1011 과 1110 은 키가 같다.(0이 1개, 1이 3개)

3) 큐브맵의 한 키에 대한 멤버가 5개가 넘으면 무한 루프를 종료하고 멤버 중 가장 작은 큐브 수를 찾는다.

실행시간 0.040 초.

/*
 	Problem 62 - Cubic permutations
*/
	
#include <iostream>
#include <ctime>
#include <map>
#include <array>
#include <vector>
#include <string.h>
#include <cmath>

using namespace std;

std::map< std::array<int,10>, vector<unsigned long int>> cubemap;

int main(int argc, char** argv)
{
	clock_t begin = clock();
	/* starting code */
	for(int i=1;; i++)
	{
		char buf[1024] = {'0',};
		unsigned long int cubenum = pow(i, 3);
		sprintf( buf, "%lu", cubenum);

		std::array<int, 10> arr = {0,0,0,0,0,0,0,0,0,0};
		for(int j=0; j<strlen(buf); j++)
		{
			int val = buf[j] - '0';
			arr[val]++;
		}

		// dbg
		/*
		for( const auto&s : arr) std::cout << s << ' ';
		cout << endl;
		*/
		
		auto it = cubemap.find( arr);
		if( it == cubemap.end()) {
			std::vector<unsigned long int> v;
			v.push_back( cubenum);
			cubemap.emplace( arr, v);
		} else {
			it->second.push_back( cubenum);

			if (it->second.size() == 5) {
				cout << "found! i=" << i << endl;
				unsigned long int mincub;
				for(int j=0; j<it->second.size(); j++)
				{
					if( j == 0) { 
						mincub = it->second[j]; 
					} 
					if( mincub > it->second[j]) {
						mincub = it->second[j];	
					}
				}
				cout << "mincub=" << mincub << endl;
				break;
			} 
		}
	}

	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}