SWEA 1244번 [S/W 문제해결 응용] 2일차 - 최대 상금 C++ 그리디 알고리즘, 시뮬레이션

리뷰

 

처음엔 주어진 자릿수와 최대 교환 횟수가 적기에 완전 탐색으로 구현하려 했으나 최대 교환 횟수를 모두 소진해야 하기에 백트래킹 구현 시 시간 초과가 출력되었다.

따라서 최적의 조건만 생각하는 그리디 알고리즘으로 접근하니 숩게 풀렸다.

D3 난이도에서 너무 어렵게 생각했던 것 같다.

 

 

SW Expert Academy

 

 

문제 풀이

1. 각 테스트 케이스에서 숫자를 스트링 s로 받아오고, 최대 교환 횟수를 k로 받아온다.
2. 정답 출력용 변수 ans를 0으로 초기화 하고 문자열 s의 크기를 length에 초기화 해준다.
3. 탐색할 문자열의 인덱스 level = 0, 교환 횟수 cnt = 0으를 재귀 함수의 매개변수로 전달하여 탐색을 시작한다.
4. 만약 현재 탐색 횟수가 k번째라면 문자열 s를 정수로 변환하여 ans 최대값을 갱신해 주고 리턴해 준다.
5. flag를 준비하고 현재 문자열의 level 인덱스보다 뒤에 더 큰숫자가 있으면 두 값을 바꿔주고 재귀를 호출한다.
6. 만약 더 큰값이 없을 경우 현재 이미 가장 큰 값인 상태인 것이다, 하지만 k를 모두 소진할때 까지 교환 작업이 이어져야 한다.
7. 만약 최대 교환 횟수에서 현재까지의 교환 횟수를 뺸 값이 홀수라면 두가지 케이스로 나누어 진다.
8. 문자열 내 같은 값이 있는 경우 해당 값들을 계속 바꿔주면 되기에 현재가 가장 큰 값이 된다.
9. 만약 문자열 내 같은 값이 없다면 맨 마지막 두 숫자를 서로 교환해 주어야 한다.
10. 최대 교환 횟수에서 현재까지의 교환 횟수를 뺸 값이 짝수라면 그냥 현재가 가장 큰 값이 된다.

 

참고 사항

정수를 문자열로 바꾸어 주는 것이 구현하기 쉽다.

 

정답 코드

#include<iostream>
#include<algorithm>
#include<string>

using namespace std;
int tc, k, ans, length;
string s;

void bt(int level, int cnt) {
	if (cnt == k) {
		ans = max(ans, stoi(s));
		return;
	}
	int flag = 1;
	for (int i = level; i < length - 1; i++) {
		for (int j = i + 1; j < length; j++) {
			if (s[i] < s[j]) {
				flag = 0;
				swap(s[i], s[j]);
				bt(level + 1, cnt + 1);
				swap(s[j], s[i]);
			}
		}
	}
	if (flag) {
		if ((k - cnt) % 2) {
			int flag = 0;
			for (char c = '0'; c <= '9'; c++) {
				if (count(s.begin(), s.end(), c) > 1) {
					flag = 1;
					break;
				}
			}
			if (flag) ans = max(ans, stoi(s));
			else {
				string temp = s;
				swap(temp[length - 2], temp[length - 1]);
				ans = max(ans, stoi(temp));
			}
		}
		else {
			ans = max(ans, stoi(s));
		}
		return;
	}
}

int main() {
	cin >> tc;
	for (int c = 1; c <= tc; c++) {
		cin >> s >> k;
		ans = 0, length = s.size();
		bt(0, 0);
		cout << "#" << c << " " << ans << "\n";
	}
}