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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

/*
 * 1244_최대상금_Greedy
 *  Greedy : 코드 간단, 속도 빠름
 *  	가설이 틀리면 답을 구하지 못할 수 있다. 103ms
 *  
 *  완탐 => 가지치기 144ms
 *  
 */

//  Z35_Solution_SWEA_1244_최대상금_Greedy
public class Solution {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			String s =st.nextToken(); // 숫자판
			
			Integer[] num = new Integer[s.length()];
			
			for (int i = 0; i < s.length(); i++) {
				num[i] = s.charAt(i) - '0';
			}
			
			int N = Integer.parseInt(st.nextToken()); // 교환횟수
			
			// [4] 동일한 숫자를 교환했는지 체크하기 위한 ArrayList 배열
			ArrayList<Integer>[] check = new ArrayList[10];
			for (int i = 0; i < check.length; i++) {
				check[i] = new ArrayList();
			}
			
			
			for (int i = 0; i < num.length && N > 0; i++) { // 선택 정렬, [1] 757148 1 교환 횟수까지 
				// i ~ 끝 : num[i] <-> num[maxIndex]
				
				int maxIndex = i; // 가장 큰 숫자의 index 를 담을 변수
				
				for (int j = i; j < num.length; j++) { // 최대값 위치 찾기
					if(num[maxIndex] <= num[j]) { // [2-1] 2737 1, 최대 숫자가 여러개일 때 낮은 자리 큰 숫자를 앞으로
						maxIndex = j;
					}
				}
				
				if(num[maxIndex] != num[i]) { // [2-2] 312 1 => 321, 최대 숫자가 MSB 위치 숫자와 다를때만 교환 
					// 위치 교환
					int temp = num[maxIndex];
					num[maxIndex] = num[i];
					num[i] = temp;
					N--; // 교환 횟수 감소
					
					
					// [4] 동일한 숫자를 교환 했는지 체크하기 위해 기록 후, 같은수를 2개 이상 바꿨을 때, 교환횟수의 감소 없이 내림차순 정렬해줌
					ArrayList<Integer> alNum = check[temp];
					alNum.add(maxIndex);
					if(alNum.size() > 1) { // 동일한 숫자를 2개 이상 바꾼 경우, 교환횟수 감소 없이 정렬
						Collections.sort(alNum); // 저장된 index 를 일단 정렬
						for (int j = 0; j < alNum.size(); j++) {
							int maxI = alNum.get(j);
							for (int k = j; k < alNum.size(); k++) {
								if(num[maxI] < num[alNum.get(k)]) {
									maxI = alNum.get(k);
								}
							}
							// num[maxI] <-> num[alNum.get(j)] 교환
							int tempN = num[alNum.get(j)];
							num[alNum.get(j)] = num[maxI];
							num[maxI] = tempN;
						}
					}
				}
			}
			
			// Arrays.asList(배열) : 배열을 List 로 변경해주는 메소드, 기본형타입의 배열은 안되고 객체 타입만 된다.
			HashSet<Integer> hs = new HashSet<Integer>(Arrays.asList(num));
			
			// [3] 교환 횟수가 남았으면 남은만큼 교환
			// 짝수만큼 남은 건 무시, 홀수만큼 남으면 1회 교환(LSB를 바꾸자) 321 4
			if(N % 2 == 1 && hs.size() == num.length) { // [3-1] 456789 10 => 987645
				// [3-2] 같은 숫자가 2개 이상 있는 경우는 교환회수를 무시 777770 5 => 777770
				int temp = num[num.length-1];
				num[num.length-1] = num[num.length-2];
				num[num.length-2] = temp;
			}
			
			System.out.print("#" + tc + " ");
			for (int i = 0; i < num.length; i++) {
				System.out.print(num[i]);
			}
			System.out.println();
		}
	}
}

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;

/*
 * Greedy 는 간단하고 빠르다, 또한 위험하다.
 * 완탐은 느리다, 하지만 반드시 답을 찾는다.
 * 		=> 시간을 개선하기위한 가지치기를 잘하면 (Bracktracking) 빠른 결과를 낼 수 있다.
 */

// Z35_Solution_SWEA_1244_최대상금_백트래킹
public class Solution {

	static int max;
	 static HashSet<String> set;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			String s = st.nextToken(); // 숫자판

			int[] num = new int[s.length()];

			for (int i = 0; i < s.length(); i++) {
				num[i] = s.charAt(i) - '0';
			}

			int N = Integer.parseInt(st.nextToken()); // 교환횟수\
			set = new HashSet<String>();	// 같은상태의 중복을 제거
			max = 0;
			find(num, N);
			System.out.println("#" + tc + " " + max);
			
		}
	}

	public static void find(int[] num, int N) {
		// num 배열을 10진수 숫자로 만들기
		int val = 0;
		
		for (int i = 0; i < num.length; i++) {
			val = val * 10 + num[i];
		}
		
		if(set.contains(""+val+N)) {
			return; // 검토 했던 작업이므로 리턴
		} else {
			set.add(""+val+N); // 현재 상태 저장
		}
		
		if(N == 0) { // 종료파트, 교환회수가 0이면 종료
			if(max < val) max = val;
		} else { // 임의의 2개 숫자를 골라서(조합) 교환
			for(int i=0; i<num.length-1; i++) {
				for (int j = i+1; j < num.length; j++) {
					
					int temp = num[i];
					num[i] = num[j];
					num[j] = temp;
					
					find(num, N-1);
					
					// 원복
					temp = num[i];
					num[i] = num[j];
					num[j] = temp;
				}
			}
		}
	}
}