<SWEA> #5658 set, deque_보물상자 비밀번호 c++
1. Input
-
보물 상자의 뚜껑을 시계방향으로 돌릴 때마다 비밀번호 쌍이 바뀌므로
deque
자료구조를 사용했다
(삽입과 삭제가 빈번하게 일어나지 않으므로 vector를 사용해도 된다) -
비밀번호 쌍은 중복을 허용하지 않으므로
set
자료구조를 사용했다. 이때 내림차순으로 저장되게 생성한다
(이것 또한 그냥 vector를 사용하고 저장할 때 중복된 값은 저장하지 않는 방법을 사용해도 된다)
deque<char> dq;
set<int, greater<int>> s;
void input(int N, int K) {
for (int i = 0; i < N; i++) {
char c; cin >> c;
dq.push_back(c);
}
}
2. Rotate
- 뚜껑을 오른쪽으로 회전하면 제일 끝에 있는 글자가 제일 앞으로 온다
void rotate() {
char back = dq.back();
dq.push_front(back);
dq.pop_back();
}
3. Make Number
- 전체 글자수가
N
개일 때, 각 비밀번호의 길이는N/4
이고 이 길이를M
이라 둔다 - 전체 글자수를
M
개씩 쪼개어10진수
로 만들어준다 M
개씩 쪼개어 만든 10진수를set
에push
해주면 내림차순으로 정렬된다
void make_number(int M) {
int n = dq.size();
for (int i = 0; i < n; i++) {
int number = 0;
for (int j = M-1; j >=0 ; j--) {
int a = 0;
if ('0' <= dq[i] && dq[i] <= '9') a = dq[i] - '0';
else if ('A' <= dq[i] && dq[i] <= 'F') a = (dq[i] - 'A') + 10;
number += (a * pow(16, j));
i++;
}
s.insert(number);
i--;
}
}
4. print
set
은 임의 접근이 불가능하므로 다음과 같이 반복자iter
를 사용하여 순차적으로 하나씩 접근하여K
번째로 큰 수를 찾아낸다
set<int>::iterator iter;
iter = s.begin();
for (int i = 0; i < K - 1; i++)
iter++;
cout << "#" << test_case << " " <<*iter<<endl;
Source Code
#include <iostream>
#include <set>
#include <vector>
#include <deque>
#include <math.h>
#define endl "\n"
using namespace std;
deque<char> dq;
set<int, greater<int>> s;
void init() {
dq.clear();
s.clear();
}
void make_number(int M) {
int n = dq.size();
for (int i = 0; i < n; i++) {
int number = 0;
for (int j = M-1; j >=0 ; j--) {
int a = 0;
if ('0' <= dq[i] && dq[i] <= '9') a = dq[i] - '0';
else if ('A' <= dq[i] && dq[i] <= 'F') a = (dq[i] - 'A') + 10;
number += (a * pow(16, j));
i++;
}
s.insert(number);
i--;
}
}
void rotate() {
char back = dq.back();
dq.push_front(back);
dq.pop_back();
}
void solution(int M) {
for (int i = 0; i <M; i++) {
rotate();
make_number(M);
}
}
void input(int N, int K) {
for (int i = 0; i < N; i++) {
char c; cin >> c;
dq.push_back(c);
}
}
int main(int argc, char** argv) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int test_case;
int T;
cin >> T;
for (test_case = 1; test_case <= T; ++test_case) {
init();
int N, K;
cin >> N >> K;
input(N, K);
solution(N/4);
set<int>::iterator iter;
iter = s.begin();
for (int i = 0; i < K - 1; i++)
iter++;
cout << "#" << test_case << " " <<*iter<<endl;
}
return 0;
}
Author And Source
이 문제에 관하여(<SWEA> #5658 set, deque_보물상자 비밀번호 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/SWEA-5658-set-deque보물상자-비밀번호-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)