[L38 디자이너의 손길] 문자열의 위치 변경하여 최댓값 찾기

- 강사님 코드

 ->  2중for문 이용하여 swap후 돌아올때 원상복구하기

#include <iostream>
#include <cstring>
using namespace std;

char str[100];
int n;

int maxi;
int limit;

int calc() {
	int sum = 0;
	for (int i = 1; i < n; i++) {
		char ca = str[i - 1];
		char cb = str[i];

		if (ca == cb) sum -= 50;
		if (abs(ca - cb) <= 5) sum += 3;
		if (abs(ca - cb) >= 20) sum += 10;
	}

	return sum;
}

void run(int level) {
	if (level == limit) {
		int ret = calc();		
		if (maxi <= ret) maxi = ret;
		return;
	}

	for (int a = 0; a < n - 1; a++) {
		for (int b = a + 1; b < n; b++) {
			swap(str[a], str[b]);
			run(level + 1);
			swap(str[a], str[b]);
		}
	}
}

int main()
{
	cin >> str;
	cin >> limit;

	n = strlen(str);
	run(0);
	cout << maxi;

	return 0;
}

- 제출코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

char input[10];
char cinput[10];

int path[10];
int n;

vector<pair<int, int>>tmp;

int Max = 0;

void run(int le, int st) {
	if (le == 2) {
		tmp.push_back(make_pair(path[0], path[1]));
		return;
	}

	for (int i = st; i < strlen(input); i++) {
		path[le] = i;
		run(le + 1, i + 1);
		path[le] = 0;
	}

}

void change(int a, int b) {
	char tmp = cinput[a];
	cinput[a] = cinput[b];
	cinput[b] = tmp;
}

pair<int,int> ret[10];
void run2(int le) {
	if (le == n) {
		for (int i = 0; i < strlen(input); i++) {
			cinput[i] = input[i];
		}

		for (int i = 0; i < n; i++)
			change(ret[i].first, ret[i].second);

		int sum = 0;
		for (int x = 1; x < strlen(input); x++) {
			int num = cinput[x] - cinput[x - 1];
			if (num == 0) sum -= 50;
			else if (abs(num) <= 5) sum += 3;
			else if (abs(num) >= 20) sum += 10;
		}

		//cout << cinput << " ";
		//cout << sum << endl;
		if (sum > Max)Max = sum;

		return;
	}

	for (int i = 0; i < tmp.size(); i++) {
		ret[le] = tmp[i];
		run2(le + 1);
	}
}

int main()
{
	cin >> input >> n;

	run(0,0);

	run2(0);
	
	cout << Max;

	return 0;
}