1244 SWEA 최대상금

 
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        
        for(int t= 0; t < test; t++) {
            String s = sc.next();
            String sone = new String(s);
            StringBuilder s2 = new StringBuilder(s);
            StringBuilder s3 = new StringBuilder(s);
            String none = "";
            int m = sc.nextInt();
            int index = 0;
            int index2 = 0;
            int cnt = 0;
            int cht = 0;
            char temp;
            int check= 0;
            boolean boo = false;
            for(int i = 0; i < m;) {
                boo =false;
                for(int j = 0; j< s.length();j++) {
                    index = Integer.parseInt(s);
                    cnt = Integer.parseInt(s);
                    for(int k = 0; k< s.length();k++) {
                        s2 = new StringBuilder(s);
                        temp = s2.charAt(k);
                        s2.setCharAt(k, s2.charAt(j));
                        s2.setCharAt(j,temp);
                        index2 = Integer.parseInt(s2.toString());
 
                        if(cnt < index2) {
                            cnt = index2;
                            s3 = new StringBuilder(s2.toString());
                        }
                        
                    }//endofk
                    check = 0;
                    for(int siz = 0; siz < s.length(); siz++) {
                        if(sone.charAt(siz) != s3.charAt(siz))
                            check++;
                    }
                    if(cnt > index && check == 2*m) {
                        none = s3.toString();
                        boo =true;
                    }
                    if(cnt > index) {
                        s = s3.toString();
                        if(!boo)
                            cht++;
                    }
                }//endofj
                break;
            }//endofi
            if(boo) {
            System.out.println("#" + (t+1) + " "+ none);
            }
            else {
                if(m%2 == 1)
                System.out.println("#" + (t+1) + " "+ s);
                else {
                s2 = new StringBuilder(s);
                temp = s2.charAt(s2.length()-1);
                s2.setCharAt(s2.length()-1, s2.charAt(s2.length()-2));
                s2.setCharAt(s2.length()-2, temp);
                System.out.println("#" + (t+1)+ " " +s2);
                }
            }
            
        }
    }//endof main
}//end of class
 

그리디로 푸는데 한참걸렸다.

교환하면서 나오는 최대값일때 갱신을 시켜주면서 찾는데 , 

1. 88832 와 88823 처럼 같은 수를 바꿔준 값인데 더 높은 수가 있을 수 있으므로 원래 수와의 차이를 통해 최신화시켜주었고

2. 바꿔줘야 할 수가 가장 큰 수를 만든 후에도 남아있을 경우

-> 홀수일 경우 그냥 출력,  짝수일 경우 뒤에만 바꿔준 뒤 출력하였다.