[C++] 백준 2659번: 십자카드 문제

문제 링크

2659번: 십자카드 문제

문제 요약

십자모양 카드의 각 모서리에 4개의 숫자가 주어진다. 이 카드를 회전시켜 만들 수 있는 수 중에 가장 작은 수를 '시계수'라고 한다.
십자모양 카드가 주어질 때, 해당 카드의 시계수가 1부터 9까지 숫자로 만들 수 있는 모든 시계수 중에 몇 번째로 작은 시계수인지 알아내야 한다.

접근 방법

구현 문제였습니다. 먼저 가능한 모든 시계수들의 목록을 만들고, 입력으로 받은 카드로 만들 수 있는 시계수가 몇번째에 속하는지 알아내면 됩니다.

네 자리 숫자에서 각 자리의 수를 뽑아내서 덱에 넣어준 다음에 덱의 원소를 회전시키면서 새로운 네 자리 숫자를 만들고, 그 중에 최솟값을 찾는 방식으로 시계수를 만들었습니다.

입력을 받기에 앞서 먼저 전처리로 1111부터 9999까지 반복문을 돌리며 각 자리에 0이 없는 수에 한해 시계수를 구하고 벡터에 저장해 줬습니다. 이 안에는 당연히 중복되는 수가 존재할 수밖에 없습니다. 예를 들어 1112와 1121 같은 경우 시계수가 모두 1112로 같기 때문입니다. 따라서 정렬한 뒤에 std::unique와 erase를 통해서 중복을 제거해 주었습니다.

이제 입력을 받고, 입력받은 수도 같은 방법으로 시계수를 구해줍니다. 그리고, 벡터가 정렬된 상태이기 때문에 이분탐색으로 위치를 구했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int rotate(deque<int>& dq)
{
	int ret = 10000;
	for (int i = 0; i < 4; i++)
	{
		dq.push_back(dq.front()), dq.pop_front();

		int tmp = 0;
		for (int i = 0; i < 4; i++)
			tmp += dq[i] * pow(10, 3 - i);
		ret = min(ret, tmp);
	}

	return ret;
}

int main(void)
{
	vector<int> v;
	for (int i = 1111; i <= 9999; i++)
	{
		deque<int> tmp;
		int num = i;
		for (int j = 1000; j >= 1; j /= 10)
			tmp.push_back(num / j), num %= j;

		bool flag = false;
		for (auto& j : tmp)
			if (!j)
				flag = true;

		if (!flag)
			v.push_back(rotate(tmp));
	}

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	deque<int> input(4);
	for (int i = 0; i < 4; i++)
		cin >> input[i];

	cout << lower_bound(v.begin(), v.end(), rotate(input)) - v.begin() + 1 << endl;
	return 0;
}