[백준 2659] 십자카드 문제 (C++)

https://www.acmicpc.net/problem/2659

문제

---

위와 같은 십자모양의 한 장의 카드에서, 네 모서리에 1 이상 9 이하의 숫자가 하나씩 씌여 있다. 이 네 개의 숫자 중에는 같은 숫자도 있을 수 있다.

모든 가능한 십자 카드가 주어질 때, 각각의 카드는 다음과 같은 '시계수'라는 번호를 가진다. 시계수는 카드의 숫자들을 시계 방향으로 읽어서 만들어지는 네 자리 수들 중에서 가장 작은 수이다. 위 그림의 카드는 시계방향으로 3227, 2273, 2732, 7322로 읽을 수 있으므로, 이 카드의 시계수는 가장 작은 수인 2273이다.

입력으로 주어진 카드의 시계수를 계산하여, 그 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 알아내는 프로그램을 작성하시오.

예를 들어서, 다음과 같은 십자 카드의 시계수는 1122이며, 이 시계수보다 작은 시계수들은 1111, 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119 뿐이므로 1122는 10번째로 작은 시계수다. (여기서 십자카드는 0 이 나타날 수 없으므로 1120은 시계수가 될 수 없다. 또한 1121 이 적혀있는 카드의 시계수는 1112이므로, 1121은 시계수가 될 수 없다.

 

입력

---

입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다.

 

출력

---

입력된 카드의 시계수가 모든 시계수들 중에서 몇 번째로 작은 시계수인지를 출력한다.

 

문제 풀이

---

브루트 포스 문제.

12시부터 시계방향대로 네 모서리를 a, b, c, d라 하면 시계수는 1000a+100b+10c+d, 1000b+100c+10d+a, 1000c+100d+10a+b, 1000d+100a+10b+c 중 가장 작은 수이다.

4중 for 문을 이용하여 모든 수의 시계수를 구해 set에 저장한 후, 입력 받은 네 숫자로 얻을 수 있는 시계수를 구한다. 그 후 set에서의 해당 수가 몇번째에 위치해 있는지 확인하면 된다.

 

아래는 코드.

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
set<int> clockNums;

int calc(int a, int b, int c, int d)
{
	return a * 1000 + b * 100 + c * 10 + d;
}

int getClockNum(int a, int b, int c, int d)
{
	int A = calc(a, b, c, d);
	int B = calc(b, c, d, a);
	int C = calc(c, d, a, b);
	int D = calc(d, a, b, c);
	return min({ A, B, C, D });
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int a, b, c, d;
	for (int i = 1; i <= 9; i++)
	{
		for (int j = 1; j <= 9; j++)
		{
			for (int k = 1; k <= 9; k++)
			{
				for (int l = 1; l <= 9; l++)
				{
					clockNums.insert(getClockNum(i, j, k, l));
				}
			}
		}
	}
	cin >> a >> b >> c >> d;
	int findClockNum = getClockNum(a, b, c, d);
	int index = distance(clockNums.begin(), lower_bound(clockNums.begin(), clockNums.end(), findClockNum));
	cout << index+1 << "\n";
	return 0;
}