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

SW Expert Academy

 

 

 

나의 풀이

이 문제는 2가지의 조합을 이용해서 해결하였습니다.

 

첫번째 조합은 교환할 수 있는 모든 가짓수를 구한 조합입니다. 예를 들어 1, 2, 3의 원소가 있다면 (1, 2), (1, 3), (2, 3) 이렇게 3가지의 교환할 수 있는 가짓수가 나오게 됩니다.

 

두번째 조합은 이렇게 구한 가짓수에서 중복을 포함해서 교환할 원소를 횟수만큼 구합니다. 예를 들면 위에서 구한 가짓수에서 첫번째 교환을 3번, 첫번째 교환을 2번 두번째 교환을 1번 등등 이런식으로 진행합니다.

 

2가지 조합으로 구한 위치를 교환한 결과를 구하고 이를 변수에 최대값으로 저장합니다.

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

class Solution
{
	
	static List<List<Integer>> combiList = new ArrayList<List<Integer>>();
	static int answer = 0;
	public static void main(String args[]) throws Exception
	{
		
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T;
		T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			answer = 0;
			combiList.clear();
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int[] board = Arrays.stream(st.nextToken().split("")).mapToInt(Integer::parseInt).toArray();
			int exchangeCnt = Integer.parseInt(st.nextToken());
			combination(0, 0, board);
			swapCombination(0, 0, exchangeCnt, board);
			
			System.out.println("#" + test_case + " " + answer);
		}
	}

	static List<Integer> combi = new ArrayList<Integer>();
	static void combination(int cnt, int start, int[] board) {
		if (cnt == 2) {
			combiList.add(new ArrayList<>(combi));
			return;
		}
		
		for (int i = start; i < board.length; i++) {
			combi.add(i);
			combination(cnt + 1, i + 1, board);
			combi.remove(combi.size() - 1);
		}
	}
	
	static List<Integer> swapCombi = new ArrayList<Integer>();
	static void swapCombination(int cnt, int start, int target, int[] board) {
		if (cnt == target) {
			answer = Math.max(answer, swap(swapCombi, board));
			return;
		}
		
		for (int i = start; i < combiList.size(); i++) {
			swapCombi.add(i);
			swapCombination(cnt + 1, i, target, board);
			swapCombi.remove(swapCombi.size() - 1);
		}
	}
	
	static int swap(List<Integer> swapCombi, int[] board) {
		int[] tempBoard = board.clone();
 		for (int combi : swapCombi) {
			int first = combiList.get(combi).get(0);
			int second = combiList.get(combi).get(1);
			int temp = tempBoard[first];
			tempBoard[first] = tempBoard[second];
			tempBoard[second] = temp;
		}
		
		return Integer.parseInt(Arrays.toString(tempBoard).replaceAll("[^0-9]",""));
	}
}