✔문제링크

SWEA1244. 최대 상금

📝문제설명

숫자판을 주어진 횟수만클 교환시켜 가장 큰 숫자를 만들어야 한다. 이때, 가장 큰 수가 완성되어도 교환 횟수가 남았다면 교환을 진행해야 한다.

💡해결방법

결론부터 말하자면 그리디 방법으로 문제를 풀려고 시도를 해보았으나 실패했다.😭 선택정렬과 앞에서부터 숫자를 하나 고정하고 뒤를 탐색하여 교환대상이 될 가장 큰 수를 가져오는 방법을 시도했으며 발생할 수 있는 예외 상황에 대한 처리를 했다.
예를들면, 777770을 5번 교환하면 맨 끝의 2자리의 교환을 진행했는데

이를 예외 처리를 통해 잡아줬다. 그러나, 다음과 같은 경우의 예제의 해결법을 찾지 못했다. 32888을 2번 교환하는 경우 88832가 나와야 하는데 뒷자리부터 교환하다 보니 아래와 같이 88823의 결과값이 나온다. 아직 해결책을 찾지 못했다 고민을 해봐야겠다.ㅠㅠ

👍코드

package com.algorithm01.basic;

import java.util.ArrayList;
import java.util.Scanner;

/*
1
777770 5
 ======= 
1
32888 2

*/
public class SWEA1244최대상금{
	
	static int T, N, ANS;
	static ArrayList<Integer> list;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		
		for(int tc = 0; tc<T; tc++) {
			list = new ArrayList<>();
			String tmp = sc.next();
			N = sc.nextInt();
			
			for(int i=0; i<tmp.length(); i++) {
				list.add(tmp.charAt(i)-'0');
			}
			ANS = Integer.MIN_VALUE;
			DFS(0);
			
			System.out.println("#"+(tc+1)+" " + ANS);
		}
	}
	private static void DFS(int L) {
		if(L == N) {
			int tmp = 0;
			for(int i=0; i<list.size(); i++) {
				tmp+=list.get(i)*Math.pow(10, (list.size()-1-i));
			}
			ANS = Math.max(ANS, tmp);
			return;
		}
		for(int i=0; i<list.size()-1; i++) {
			for(int j=i+1; j<list.size(); j++) {
				swap(i,j);
				DFS(L+1);
				swap(j,i);
			}
		}
		
	}
	private static void swap(int first, int second) {
		int tmp = list.get(first);
		list.set(first, list.get(second));
		list.set(second, tmp);
	}
	
}