SW Expert Academy - 5658. 보물상자 비밀번호

문제링크

• 보물상자 비밀번호

문제설명

• 보물상자 4개의 변에 16진수 숫자(0~F) 가 주어진다.
• 각 변에는 동일한 개수의 숫자가 있고, 시계방향 순으로 높은 자리 숫자에 해당하며 하나의 수를 나타낸다.
• 보물상자에 걸린 자물쇠의 비밀번호는 보물상자에 적힌 숫자로 만들 수 있는 모든 수 중 K번째로 큰 수를 10진수로 만든 수이다.
• N개의 숫자가 입력으로 주어졌을 때, 보물상자의 비밀번호를 출력하라.

문제접근

• 4개의 변이 존재하므로 각 변에 존재하는 숫자의 개수는 HEX_NUM = N/4 이다.
• 각 변에 놓인 16진수 숫자들을 시계방향 순서로 회전하는 경우 각 변에 놓인 16진수 숫자들의 수 만큼만 이동하면 모든 경우의 수를 찾을 수 있다.
• 2차원 배열 box[SIDE_NUM][HEX_NUM] 는 0~3번 변에 0 ~ HEX_NUM-1 위치하는 숫자의 정보를 담는다.
• 회전을 하면 중복되는 수가 만들어질 수 있는데, 이를 막기 위해 map 자료구조를 활용하여 중복을 확인하며 10진수로 변환된 값을 담았다.
  • set 자료구조를 활용하는 방법도 있다.
• 16진수 -> 10진수로 변환하는 로직은 재귀적으로 구현한다.

구현1

#include <iostream>
#include <string>
#include <memory.h>
#include <map>
#include <cctype>
#include <vector>
#include <algorithm>
#include <cmath>
#define MAX 7
#define SIDE_NUM 4

using namespace std;

int N, K;
int HEX_NUM, ROTATE_NUM;
char box[SIDE_NUM][MAX];
map<string, int> cand;

void updateBox(string str) {
	int side = 0;
	for (int i = 0; i < str.length(); i++) {
		if (i > 0 && ((i % HEX_NUM) == 0)) side++;
		box[side][i % HEX_NUM] = str[i];
	}
}

int getHexValue(string str, int m) {
	if (str.size() == 0) {
		return 0;
	}

	char ch = str.front();
	int val = 0;
	if (isalpha(ch)) val = ch - 'A' + 10;
	else val = ch - '0';

	return val * pow(16, m) + getHexValue(str.substr(1), m - 1);
}

void rotateBox() {
	char nBox[SIDE_NUM][MAX];
	for (int side = 0; side < SIDE_NUM; side++) {
		for (int idx = 0; idx < HEX_NUM; idx++) {
			int nSide = side;
			int nIdx = idx + 1;
			if (idx == HEX_NUM-1) {
				nSide = (side + 1) % SIDE_NUM;
				nIdx = 0;
			}
			nBox[nSide][nIdx] = box[side][idx];
		}
	}
	memcpy(box, nBox, sizeof(box));
}

void updateCand() {
	for (int side = 0; side < SIDE_NUM; side++) {
		string numStr;
		for (int idx = 0; idx < HEX_NUM; idx++) {
			numStr.push_back(box[side][idx]);
		}
		int val = getHexValue(numStr, HEX_NUM-1);
		// 중복되지 않는 경우
		if (cand.find(numStr) == cand.end()) cand[numStr] = val;
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> K;
		HEX_NUM = N / SIDE_NUM;
		ROTATE_NUM = HEX_NUM;
		memset(box, 0, sizeof(box));
		cand.clear();

		string numStr;
		cin >> numStr;
		updateBox(numStr);

		for (int i = 0; i < ROTATE_NUM; i++) {
			rotateBox();
			updateCand();
		}

		vector<int> list;
		for (auto ele : cand) {
			list.push_back(ele.second);
		}
        // 내림차순 정렬
		sort(list.begin(), list.end(), greater<int>());
		cout << "#" << test_case << " " << list[K-1] << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

구현2

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <sstream>

#define AREA_ONE 0
#define AREA_TWO 1
#define AREA_THREE 2
#define AREA_FOUR 3

#define ROTATE_NUM 3
using namespace std;

int N, K;
int passwordLen;
vector<string> list;
set<string, greater<string>> cand;

void init()
{
	list.clear();
	cand.clear();
}

void updateCand()
{
	for (auto ele : list) {
		cand.insert(ele);
	}
}

void input()
{
	init();
	cin >> N >> K;
	string str;
	cin >> str;
	passwordLen = N / 4;
	
	string tmp;
	for (int i = 0; i < str.length(); i++) {
		tmp += string(1, str[i]);
		if (tmp.length() == passwordLen) {
			list.push_back(tmp);
			tmp.clear();
		}
	}
	updateCand();
}

void rotate()
{
	string str1, str2, str3, str4;
	str1 = string(1, list[AREA_FOUR].back());
	str1 += list[AREA_ONE];
	str1.pop_back();

	str2 = string(1, list[AREA_ONE].back());
	str2 += list[AREA_TWO];
	str2.pop_back();

	str3 = string(1, list[AREA_TWO].back());
	str3 += list[AREA_THREE];
	str3.pop_back();

	str4 = string(1, list[AREA_THREE].back());
	str4 += list[AREA_FOUR];
	str4.pop_back();

	list.clear();
	list.push_back(str1);
	list.push_back(str2);
	list.push_back(str3);
	list.push_back(str4);

	updateCand();
}

void solution()
{
	for (int i = 0; i < passwordLen - 1; i++) {
		rotate();
	}

	int cnt = 0;
	string hex;
	for (auto ele : cand) {
		cnt++;
		if (cnt == K) {
			hex = ele;
			break;
		}
	}

	stringstream stm(hex);
	int hexValue;
	stm >> std::hex >> hexValue;
	cout << hexValue << endl;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		cout << "#" << test_case << " ";
		solution();
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}