[SWEA] 13428. 숫자 조작

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX4EJPs68IkDFARe 

SW Expert Academy

---

접근 방법

백트래킹을 이용해 풀었다.

한 번의 반복문에 min 계산과 max 계산을 욱여넣느라 다소 복잡해졌지만

메모리는 19,112 kb 실행 시간은 98 ms 정도로 나름 효율적이었다.

check(ck1, ck2, c1, c2) 를 이용해서 반복할 필요 없는 부분은 가지치기 해 주었다.

 

소스 코드

import java.util.*;
import java.io.*;
 
class Solution {
    static char[] n;
    static int[] min, max;
    static int x, y;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for(int t=1; t<=T; t++) {
            n = (br.readLine()).toCharArray();
            max = new int[] {0,0};
            min = new int[] {0,9};
            x = 0; y = 0;
             
            back(0, true, true);
            if(x == 0) x = Integer.valueOf(String.valueOf(n));
            if(y == 0) y = Integer.valueOf(String.valueOf(n));
            sb.append("#" + t + " " + x + " " + y + "\n");
        }
        System.out.print(sb.toString());
    }
    static void dfs(int idx, boolean c1, boolean c2) {
        if(idx == n.length)
            return;
        if(!c1 && !c2)
            return;
         
        boolean ck1 = false;
        boolean ck2 = false;
         
        for(int i=idx+1; i<n.length; i++) {
            int nn = n[i]-'0';
            int dd = n[idx]-'0';
            if(idx == 0 && nn == 0)
                continue;
             
            if(c1 && dd > nn && min[1] >= nn) {
                min[0] = i;
                min[1] = nn;
                ck1 = true;
            }
            if(c2 && dd < nn && max[1] <= nn) {
                max[0] = i;
                max[1] = nn;
                ck2 = true;
            }
        }
        if(ck1) {
            swap(idx, min[0]);
            x = Integer.valueOf(String.valueOf(n));
            swap(idx, min[0]);
            c1 = false;
        }
        if(ck2) {
            swap(idx, max[0]);
            y = Integer.valueOf(String.valueOf(n));
            swap(idx, max[0]);
            c2 = false;
        }
         
        back(idx+1, c1, c2);
    }
     
    static void swap(int a, int b) {
        char tmp = n[a];
        n[a] = n[b];
        n[b] = tmp;
    }
}