[SWEA]5658. [모의 SW 역량테스트] 보물상자 비밀번호

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

SW Expert Academy

 

풀이과정

1. 입력 받은 문자는 1~F 까지 이다. char로 받아 int로 치환하였다.

2. N / 4만큼의 수 만큼 회전을 시키며 값을 찾았다. N / 4 이후엔 초기 상태로 돌아온다.

3. 값을 찾아 중복된 값이 아니면 vector에 저장하였다.

4. 내림차순으로 정렬 후 K번째 값을 찾았다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;
typedef unsigned long long ull;

int N, K, T;
int key[28];

void rotate()
{
	int prev = key[0];
	for (int i = 1; i < N; i++) {
		int tmp = key[i];
		key[i] = prev;
		prev = tmp;
	}
	key[0] = prev;
}

bool desc(ull a, ull b) { return a > b; }

ull solution()
{
	vector<ull> v;
	int size = N / 4;
	for (int i = 0; i < size; i++) {
		ull num = 0;
		for (int j = 0; j < N; j++) {
			num += (key[j] << 4 * (size - (j%size) - 1));
			if (size - 1 == j % size) {
				if (find(v.begin(), v.end(), num) == v.end()) {
					v.push_back(num);
				}
				num = 0;
			}
		}
		rotate();
	}
	sort(v.begin(), v.end(), desc);
	return v[K-1];
}

int main()
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d", &N, &K);
		for (int i = 0; i < N; i++) {
			char ch;
			scanf(" %c", &ch);
			if (ch >= '0' && ch <= '9') {
				key[i] = ch - '0';
			}
			else {
				switch (ch) {
				case 'A': key[i] = 10; break;
				case 'B': key[i] = 11; break;
				case 'C': key[i] = 12; break;
				case 'D': key[i] = 13; break;
				case 'E': key[i] = 14; break;
				case 'F': key[i] = 15; break;
				}
			}
		}
		printf("#%d %llu\n",tc, solution());
	}
}