[SWEA] 1244. [S/W 문제해결 응용] 2일차 - 최대 상금 - JAVA

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD 

풀이

어려운 문제였다.

처음에는 수를 정해서 바꿀려고 시도했다. 시도하다보니 경우의 수가 많이 나오게 되고 이는 틀린 풀이임을 직감하게 되었다.

따라서 완전탐색을 이용하여 숫자를 모두 교환하여 모든 수를 찾고 그중에서 가장 큰 수를 구하는 방식으로 하게 되었다.

 

근데, 이렇게 하면 시간초과가 발생하기때문에 최적화가 필요하다.

 

샘플 input인 456789, 10 으로 예를들어보자.

이 경우의 정답은 987645 다. 이는 즉, 여러번 교환해도 결과값은 최댓값이 아닐 수 있다는 것을 의미한다. 또한, 교환 횟수를 맞추기 위해 맨 끝 두자리로 교환을 했다는 것을 생각할 수 있다. 

만약 11번 교환할 경우 987654가 되고, 12번 교환할 경우 987645, 13번 987654 ... 이런 식으로 계속 나아갈 것이라고 유추할 수 있다.

 

456789는 3번의 교환만에 987654(최댓값)을 만들 수 있고 이후 4번 교환시 987645, 5번 987654, 6번 987645 ... 이렇게 진행된다.

 

다른 예시인 12345 5 는 2번의 교환만에 54321을 만들 수 있다. 이후 3번 54312, 4번 54321, 5번 54312 이므로 정답은 54312 이 된다.

즉, 입력받은 문자열 길이 만큼 교환을 하면 정답을 얻을 수 있다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int arr[];
	static int cnt;
	static int max = 0;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			st = new StringTokenizer(br.readLine());
			String val = st.nextToken();
			cnt = Integer.parseInt(st.nextToken());
			
			arr = new int[val.length()];
			
			for(int i=0;i<val.length();i++) {
				arr[i] = val.charAt(i) - '0';
			}
			
			if(cnt > arr.length) {	
            	cnt = arr.length;	
			}
			
			max = 0;
			back(0, 0);
			
			System.out.println("#"+test_case+" "+max);

		}
		
	}
		
	static void back(int start, int depth) {
		if(depth == cnt) {
			String str = "";
			for(int i=0;i<arr.length;i++) {
				str += arr[i];
			}
			max = Math.max(max, Integer.parseInt(str));
			return;
		}
		
		for(int i=start;i<arr.length;i++) {
			for(int j=i+1;j<arr.length;j++) {
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				
				back(i, depth+1);
				
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				
			}
		}
	}
	
}