<SWEA> #5658 set, deque_보물상자 비밀번호 c++

SWEA #5658

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;
}