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

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

SW Expert Academy

SWEA 모의 역량테스트 문제 중 하나인 보물상자 비밀번호 문제이당

회전 상태

면을 회전시켜 나올 수 있는 한 면(B3B, E1B 등)으로 표현될 수 있는

16진수 중 K번째로 큰 수를 10진수로 표현하는 문제이다

 

N의 최댓값은 28 👉 숫자는 최대 7자리(16진수)

표현될 수 있는 숫자의 최댓값은 FFFFFFF = ‭268,435,455‬ 이기 때문에 int형을 사용해도 무방

 

숫자는 char형으로 한꺼번에 저장해준 다음

인덱스 연산을 사용하여 회전과 각 면에 따른 숫자를 구하는 방식을 사용했다!

 

예를들어 F53586D76286B2D8에서 'D762' 부분의 숫자를 구하고 싶다면

회전을 2번 했을 때

(왼쪽위 면이 0번째 면이라고 했을 때)1번째 면에 있는

숫자 (16/4)개를 구하면 된다!!

계산과정

수식에 있는 str[(rot+i*m+j)%n]이 원하는 위치의 문자를 구할 수 있는 계산식이다

이런식으로 모든 경우의 수의 숫자를 구하고 정렬하여 K번째로 큰 숫자를 출력하면 된다

 

#include <cstdio>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
int tc, n, k, ans;
char str[30], c;
vector<int> v;
int main() {
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++) {
		scanf("%d%d", &n, &k);
		scanf(" %s", str);
		int m = n / 4;

		for (int rot = 0; rot < m; rot++) {//회전
			for (int i = 0; i < 4; i++) {//각 면 계산
				int sum = 0, check = 1;
				for (int j = 0; j < m; j++) {
					c = str[(rot + i * m + j) % n];
					if (c >= '0' && c <= '9')
						sum += (int)(c - '0')*pow(16,m-j-1);
					else
						sum += (int)(c - 'A' + 10)*pow(16,m-j-1);
				}
				for (auto f : v) {
					if (sum == f)check = 0;
				}
				if (check)v.push_back(sum);
			}
		}
		sort(v.begin(), v.end());
		ans = v[v.size() - k];
		v.clear();

		printf("#%d %d\n", t, ans);
	}
	return 0;
}

시간복잡도 : O(n^2)

 

++Tip. 테스트케이스는 순서를 바꿔서도 실행시켜보자