[SWEA] 최대 상금 (정렬)

alirz-pixel·2024년 6월 2일

SWEA

목록 보기

1/1

정답률	35.78
시간제한	10초
메모리 제한	힙, 정적: 256MB, 스택: 1MB

📚 해설 및 코드

✏️ 문제 접근

해당 문제는 테스트 케이스마다 주어지는 입력값의 크기가 크지 않으므로 (최대 자릿수: 6, 최대 교환 횟수: 10) DFS를 이용한 브루트 포스로 해결할 수 있다.

하지만 문제를 그대로 해석하여 정렬로도 풀 수 있다.

정렬 풀이

해당 문제를 정렬로 풀 때에는 정렬의 한 step의 결과가 최대가 되도록 하는 것이 중요하다

정렬 풀이 예외 케이스

정렬 풀이로 풀게 되면 예외 케이스가 발생하게 된다.
(output를 보면 알겠지만, 문제의 답이 정렬의 결과랑 다르기 때문이다)

1) 숫자 카드에 중복된 값이 있을 경우

해당 예외 케이스는 정렬의 한 step 당 결과가 최대가 되도록 하는 것에 집중한다면 문제가 되지 않을 수 있다.

문제의 예제를 보도록 하자

input
숫자 카드: 3, 2, 8, 8, 8 | 교환 횟수: 2

step1: 8, 2, 8, 8, 3
step2: 8, 8, 8, 2, 3
answer: 8, 8, 8, 3, 2 (wrong!)

위의 예제처럼 그리디 시점으로 봤을 때 정렬의 각 step이 최대가 되기 위해선
8 중에서도 제일 마지막에 위치한 값과 맨 앞의 카드를 바꾸면 된다.
그러나 answer의 값을 보면 그렇지 않을 것을 확인할 수 있다.

그렇기 때문에 정렬 풀이로 진행할 때는 다음 문장의 차이를 주의해야 한다.

각 step에 대해 최선을 고르는 것이 아닌, step의 결과가 최대가 나오도록 해야 한다.

2) 정렬을 수행하고도 교환 횟수가 남았을 경우

해당 예외 케이스는 정렬 수행 후의 남은 교환 횟수에 대해
어쩔 수 없이 끝의 두 자리를 swapping을 해야 하기 때문에 발생하는 예외 케이스이다.

남은 교환 횟수가 홀수라면: 끝의 두 자리를 교환해야만 한다.
남은 교환 횟수가 짝수라면: 정렬 수행 결과를 반환한다.

추가로 주의해야 할 점이 있다.
숫자 카드 중에 중복된 값이 있다면, 중복된 값끼리 교환하면 되므로 해당 예외를 고려하지 않아도 된다.

📑 코드

#include <iostream>
#include <vector>
#include <string>
#include <set>

using namespace std;


int main() {
	int T;
	cin >> T;

	for (int i = 1; i <= T; i++) {
		string num;
		int max_change_cnt;
		cin >> num >> max_change_cnt;

		// 1. 선택 정렬 수행
		int cur_change_cnt = 0;
		bool exist_same_val = false;
		vector<int> is_changed(num.length()); // 어느 숫자 카드로 인해 스왑되었는지를 저장
		for (int i = 0; i < num.length() - 1; i++) {
			int max_idx = i;

			for (int j = i + 1; j < num.length(); j++) {
				if (num[max_idx] <= num[j]) {
					max_idx = j;
				}

				if (num[i] == num[j]) {
					exist_same_val = true;
				}
			}

			// 현재 step에서 이미 최대값인 경우
			if (max_idx == i)
				continue;

			cur_change_cnt++;
			is_changed[max_idx] = num[max_idx]; // swap 된 결과를 기준으로 max_idx번 째는 num[i]의 값에 의해 swap 되었음을 의미
			swap(num[max_idx], num[i]);

			// 정렬 한 step의 결과가 최대가 되도록 하기 위해 추가 정렬 수행
			//  -> 추가 정렬시 is_changed 고려
			for (int j = i; j < num.length() - 1; j++) {
				if (!is_changed[j]) // swap 된 적이 없는 숫자 카드는, 추가 정렬을 수행해선 안됨
					continue;

				max_idx = j;
				for (int k = i + 1; k < num.length(); k++) {
					// 예외 1) 숫자 카드에 같은 값이 있을 경우에 문제가 됨
					//   => 이를 판단하기 위해 is_changed를 사용
					if (is_changed[j] == is_changed[k] && num[max_idx] < num[k]) {
						max_idx = k;
					}
				}

				if (max_idx == j)
					continue;
				swap(num[max_idx], num[j]);
			}

			// 정렬 횟수를 모두 소모함
			if (cur_change_cnt == max_change_cnt)
				break;
		}

		// 2. 숫자카드 중 중복된 값이 없다면,
		//  2-1. 남은 횟수가 홀수라면 맨 끝 2개의 숫자 swap
		//  2-2. 남은 횟수가 짝수라면 무시
		if (!exist_same_val && (max_change_cnt - cur_change_cnt) % 2) {
			swap(num[num.length() - 1], num[num.length() - 2]);
		}
		cout << "#" << i << " " << stoi(num) << "\n";
	}

	return 0;
}

alirz-pixel