1244. 최대 상금

---

package test;

import java.io.IOException;
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);

		 int test = sc.nextInt();

		 for (int k = 0; k < test; k++) {
			 
			 
			 String value = sc.next();
			 int change = sc.nextInt();
			 int size=value.length();
			 
			 int array[] = new int[size];
			StringBuilder sb = new StringBuilder();
			 
			 int max=0;
			 int sum=0;
			 int repact = (size*(size-1))/2;
			 
			 for(int i=0; i<size; i++) {
				 array[i] = Integer.parseInt(value.substring(i, i+1));
			 }
			 

			 
			 for(int i=0; i<change; i++) {
				 
				 for(int j=0; j<repact; j++) {
					 
					 for(int z=j+1; z<size; z++ ) {
						 int temp = array[j];
						 array[j] = array[z];
						 array[z] = temp;
						 
						 
						 
						 for(int x=0; x<size; x++) {
							 sb.append(array[x]);							

						 }
						 if(max<Integer.parseInt(sb.toString())){
							 max =Integer.parseInt(sb.toString());
							 
						 }
						 sb.setLength(0);
						 
						 temp = array[j];
						 array[j] = array[z];
						 array[z] = temp;
						 
					 }
					 
					
				 }
				 
				 //
				 for(int y=0; y<size; y++) {
					 array[y] = Integer.parseInt(Integer.toString(max).substring(y, y+1));
				 }
				 
			 }

		
		
		System.out.println("#"+(k+1)+" "+max);

		}
	}
	
	

}

전체를 고려하지 않고 한번 바꿀때 최대값만을 고려하여 바꿔서 결과적으로 오답이되었다.

 

재귀를 사용하여 전체적으로 해당 번수만큼 바꿨을때 최대의 수를 구해야한다.

 

코드는 https://m.blog.naver.com/hoons_612/221920673698 여기서 가져왔습니다.

package test;
import java.util.Scanner;

public class Solution {
    static int chance;
    static int answer;
    static String[] target;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        sc.nextLine();

        for(int test_case = 1; test_case<= T; test_case++) {
            String input = sc.nextLine();
            String[] inputArray = input.split(" ");

            target = inputArray[0].split("");
            chance = Integer.valueOf(inputArray[1]);

            answer = 0;
            answer = dfs(0, 0);

            System.out.println("#" + test_case + " " + answer);
        }
    }

    static int dfs(int k, int count) {
        String temp;
        String targetnum = "";

        if(chance == count) { 
            for (String tmp: target) {
                targetnum += tmp;
            }
            if(Integer.valueOf(targetnum) > answer) {
                answer = Integer.valueOf(targetnum);
            }
            return answer;
        }


        for(int i=k; i<target.length; i++) {
            for(int j=i+1; j<target.length; j++) {

                if(Integer.valueOf(target[i]) <= Integer.valueOf(target[j])) {
                    temp = target[i]; 
                    target[i] = target[j];
                    target[j] = temp;
                    dfs(i, count+1);
                    temp = target[i]; 
                    target[i] = target[j]; 
                    target[j] = temp; 
                }
            }
        }
        return answer;
    }


}