보물상자 비밀번호
문제 해석
4변으로 되어있는 보물상자에 적힌 숫자를 시계방향으로 돌려가며 만들 수 있는 수 중, K번째로 큰 숫자를 구하는 문제입니다.
각 숫자는 16진수(0~F)로 되어있으며, 중복된 숫자는 카운트하지 않습니다.
설계(10)
정확히 N/4 - 1번 숫자 위치를 움직이면서 만들 수 있는 숫자를 모두 벡터에 저장 후 정렬하여 찾으면 되는 문제입니다.
먼저, 시작위치를 0~N/4-1까지 정합니다.
이후 해당 시작위치부터 N/4개만큼 잘라내어 10진수로 변환한 후, 벡터에 저장합니다.
만약 해당 인덱스의 범위가 넘어가면 0부터 다시 시작하도록 조치를 취해줍니다.
벡터를 정렬 후, unique함수를 이용하여 중복된 숫자를 제거합니다.
구현(20)
코드
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
string s;
int N, K;
vector<int> vt;
int Convert(string tmp_s) {
int sum = 0;
int idx = 0;
for (int i = tmp_s.length()-1; i >=0; i--) {
if (tmp_s[i] >= '0' && tmp_s[i] <= '9') sum += pow(16,idx++)*(tmp_s[i] - '0');
else sum += pow(16, idx++)*(tmp_s[i] - 'A' + 10);
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int test_case = 1; test_case <= t; test_case++) {
vt.clear();
cin >> N >> K;
cin >> s;
int len = 0;
for (int i = 0; i < N / 4; i++) {
int total_cnt = 0;
int cnt = 0;
int idx = i;
string tmp_s = "";
while (total_cnt < 4) {
if (cnt == N / 4) {
int num = Convert(tmp_s);
vt.push_back(num);
tmp_s = "";
cnt = 0;
total_cnt++;
}
if (idx == N) idx = 0;
tmp_s += s[idx++];
cnt++;
}
}
sort(vt.begin(), vt.end());
vt.erase(unique(vt.begin(), vt.end()), vt.end());
printf("#%d %d\n",test_case, vt[vt.size() - K]);
}
return 0;
}
디버깅
K번째로 큰 숫자를 찾는데, 조건이 만들 수 있는 숫자 중에 K번째 숫자를 출력해야하기 때문에 해당 벡터의 사이즈를 기준으로 K번째 숫자를 찾아야 합니다.
그러나 저는 그냥 N을 기준으로 K번째 숫자를 찾는 실수를 하였습니다.
제출결과
7 ms
마무리
단순 시뮬레이션 문제였습니다. 16진수를 10진수로 변환하는 것, 시계방향으로 돌리는 부분, 중복된 숫자를 처리하는 방법 등의 테크닉이 필요한 문제입니다.