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

문제 링크: 링크

 

테스트 케이스 1번

Sliding window를 사용하면 됩니다. 비밀번호 길이가 상자의 한 변의 길이니까 윈도우 사이즈는 n/4입니다.

 

이런식으로 슬라이딩 윈도우를 사용했고요 맨 뒤랑 앞에 이어지는 부분 신경쓰셔야 합니다.

비밀번호를 모아두는 컨테이너는 set을 사용을 했는데요, 중복된 값이 나올 수 있기도 하고, 그냥 귀찮기도 하고.. 해서 set을 써봤습니다.

 

내림차순으로 정렬된 순서에서 k번째 값을 구해야 하기 때문에 greater를 사용해 set이 내림차순으로 정렬되도록 만들었고요, 오름차순 set을 써도 되지만 그러면 중복된 값이 생길 때 set의 크기가 n이 아닐 수 있다는 점을 알고계셔야 합니다.

 

hex to dec는 다 아시겠지만.. \(1B3_{(16)}=1 \times 16^2 + 11 \times 16^1 + 3 \times 16^0 = 435\) 요런식으로 하시면 됩니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef long long int lli;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t;
	cin >> t;
	for (int tc = 1; tc <= t; ++tc) {
		int n, k;
		string s;
		cin >> n >> k >> s;
		
		set<lli, greater<lli>> password;
		for (int i = 0; i < n; ++i) {
			//sliding window
			lli pass = 0;
			const int& window_sz = n / 4;
			for (int j = 0; j < window_sz; ++j) {
				const char& cc = s[(i + j) % n];
				pass += (isdigit(cc)?cc-'0':cc-'A'+10) * pow(16, window_sz-(j+1));
			}
			password.insert(pass);
		}

		auto it = password.begin();
		for (int i = 0; i < k-1; ++i)
			++it;
		cout << "#" << tc << " " << *it << "\n";
	}



	return 0;
}

long long int를 사용을 했는데, n<=28이기 때문에 n==28일 때 비밀번호의 값이 FFFFFFFF 이런식으로 들어오면 signed int는 오버플로우가 나겠거니 하고 lli를 썼습니다.

근데 int로 바꿔봤는데 통과되는거 보니까 테스트 데이터 셋이 그렇게 빡세게 들어있지는 않네요.

 

이 문제는 난이도가 안적혀있는데 D2~3 정도 되는 것 같습니다.