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

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

[코드]

import java.util.*;

public class 최대상금 {
	static int reuslt;
	static String[] arr;
	static int max,n;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt(); // 테스트케이스
		
		for(int k=1;k<=t;k++) {
			arr=sc.next().split("");
			n=sc.nextInt(); // 이동 횟수
			max=0;
			
			// 숫자의 길이보다 이동 횟수가 많으면 자릿수 만큼 이동 가능 -> 없으면 시간초과
			if(arr.length<n)
				n=arr.length;
			
			DFS(0,0);
			System.out.println("#"+k+" "+max);
		}
	}
	
	// DFS 알고리즘을 사용하여 arr 배열의 모든 자리를 바꿔보는 완전탐색 수행
	static void DFS(int depth, int start) {
		if(depth==n) { // n번의 이동을 완료했다면 최댓값 갱신
			String temp="";
			
			for(int i=0;i<arr.length;i++)
				temp+=arr[i];
			
			max=Math.max(max, Integer.parseInt(temp));
			return;
		}
		
		for(int i=start;i<arr.length;i++) {
			for(int j=i+1;j<arr.length;j++) {
				// 자리 변경
				String temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
				
				DFS(depth+1,i);
				
				// 값 되돌리기
				temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
		}
		
	}
}

 

[고찰]

 처음에는 가장 큰 숫자를 어떻게 만들어야 하는지에 집중하며 나름대로 규칙을 찾아보려 했지만 이를 코드로 옮기기에는 한계에 부딪혀 다른 사람의 해결 방식을 참고했다. 이 문제는 DFS 알고리즘을 사용하여 모든 자리를 바꿔보며 최댓값을 찾는 문제였다. 해결 방법을 보니 이제야 코드를 짤 수가 있었다. 

 하지만 DFS 알고리즘만을 사용하여 코드를 제출하면 시간초과를 받는 문제가 생겼다. 이동 횟수가 입력된 숫자의 자릿수보다 큰 경우를 처리해 주지 않으면 시간 초과로 오답을 받기 때문에 반드시 해당 부분의 예외처리를 해주어야 한다.