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

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

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개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다.

출력

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

 

< 구해야 하는 게 뭔지 파악하기 >

숫자 4개가 주어지고, 시계방향으로만 돌아갈 수 있을 때 만들어질 수 있는 최소값을 시계값이라고 한다.

그 시계값을 구했을 때, 그 시계값보다 작은 시계값이 몇개 존재하는지 구해야하는 문제이다.

 

구해야하는 걸 알았으니 어떻게 해야할까?

< 사용할 자료구조 판단 및 알고리즘 파악하기 >

나는 어처피 4개의 수로 만들어낼 수 있는 시계값의 경우의 수는 4개만 존재한다고 판단했고, 그 시계값을 하나하나 만들어보기 위해서 덱이라는 자료구조를 써야겠다고 생각했다. 앞에서 빼고 뒤에 붙이고, 위 과정으로 최소값을 구하자.

-> 시계값을 구하기 위해 덱이라는 자료구조를 통해 앞에서 빼고 뒤에 추가하는 과정으로 4번 반복을 통해 최소가 되는 시계값을 구헌다.

 

위 과정으로 시계값을 구했다면, 다음으로 알아내야하는 것은 내가 구한 시계값보다 작은 시계값이 몇 개인가?

이것이다. 이건 어떻게 구해야할까

어처피 시계값의 최초시작값은 1111이 된다. (1부터 9까지의 수만 사용)

그리고 1111부터 내가 구한 시계값까지 하나 하나 검사해주는 방법으로 할 것 같다. 어처피 4자리 수밖에 되지 않고, for문을 통해 해도 1만번이 넘지 않기에 시간복잡도 문제는 생각하지 않아도 될 것이다.

 

0이 존재하는 수는 배제해야하는 거 아닌가?

-> 어처피 0이 존재하는 수의 시계값을 구하려한다면 자리수가 줄어들 수 밖에 없다.

0이 앞에 오게 되는 순간 자리수가 줄어들기 떄문

 

그럼 for문을 통해 1111부터 내가 구한 시계값까지의 수를 x로 한다면 그 x가 될 수 있는 시계값을 구한다.

int isCircleNum(int num) {
	int temp = num;
	for (int i = 0; i < 3; i++) {
		num = num % 1000 * 10 + num / 1000;
		if (temp > num) temp = num;
	}
	return temp;
}

위 코드는 하나의 수의 시계값을 판단하는 것이다. 3번의 반복을 통해 시계값을 확인하는 건데 맨 처음에 함수로 전달받는 수를 저장해주고, 전달받은 수를 반복문을 통해 (앞에서 하나의 수를 빼고 뒤에 붙이는 과정) 저장한 수보다 작아지게 될 경우 저장된 수를 작아진 수로 변경하는 것이다. 그리고 마지막에 그 수를 반환하는 건데 반환값이 맨 처음 함수로 전달한 값과 다르다는 것은 내가 입력한 4개의 수로 만들 수 없는 시계값이라는 것을 의미하기 때문에 개수를 세지 않는다

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321
using namespace std;

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

int isCircleNum(int num) {
	int temp = num;
	for (int i = 0; i < 3; i++) {
		num = num % 1000 * 10 + num / 1000;
		if (temp > num) temp = num;
	}
	return temp;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	deque<int> dq;
	// 기준점을 덱에 푸쉬해서 4자리의 수를 만듬
	for (int i = 1; i <= 4; i++) {
		int x; cin >> x;
		dq.push_back(x);
	}

	int minV = INF;
	for (int i = 1; i <= 4; i++) {
		int val = 0; int s = 3;
		for (int j = 0; j < dq.size(); j++) {
			int data = dq.front();
			dq.pop_front();
			val += (data * (int)pow(10, s));
			s--;
			dq.push_back(data);
		}
		minV = min(minV, val);
		int x = dq.front();
		dq.pop_front();
		dq.push_back(x);
	}
	//cout << "Min Vale : " << minV << endl;

	int Answer = 0;
	for (int i = 1111; i <= minV; i++) {
		if (isCircleNum(i) == i) Answer++;
	}
	cout << Answer << endl;

	return 0;
}