SW expert 1244번 최대 상금 - 자바 java DPS

레스고

 

처음엔 쉬워 보였다, 최대자릿수가 6자리 기도 하고..

교환 횟수를 홀수와 짝수를 나누어서 큰수 찾아서 비교,,, 아 할게 많구나 싶었다.

아니면 그리디 방식으로 해야하나? 했다가 6자리니까 DPS로 풀어보자 했다.

 

DPS는 완전 탐색으로 자물쇠가 000부터 999까지라면 모든 수를 넣어서 열어보는 방식이다.

 

import java.util.*;
 
class Solution {
 
    public static int result;
 
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            int number = sc.nextInt(); // 숫자
            int cnt = sc.nextInt();    // 조작 횟수
 
            int[] numbers = new int[6]; // 최대 길이는 6 
            int len = 0;
            while (number > 0) { // 숫자 배열로 옮겨주기
                numbers[len++] = number % 10;
                number /= 10;
            }
 
            result = 0;
          
            if (len < cnt) // 조작횟수가 더 많다면
                cnt = len; // 의미없으므로 줄여주기.
            dfs(cnt, 0, numbers, len); // dfs 함수 실행
 
            // 3. Output
            System.out.printf("#%d %d%n", test_case, result);
        }
    }
 
    public static void dfs(int cnt, int start, int[] numbers, int len) {
        //Base case
        if (cnt == 0) { // 모든 조작을 완료했다면.
            int current = arrToInt(numbers, len); // 배열을 숫자로
            if (current > result) {
                result = current;
            }
            return;
        }
        // 교환
        for (int i = start; i < len - 1; ++i) {  
            for (int j = i + 1; j < len; ++j) {
                swap(numbers, i, j); // 숫자 교환
                dfs(cnt - 1, i, numbers, len); // 재귀호출로 반복
                swap(numbers, i, j); // 다시 원래 위치로
            }
        }
    }
 
    // 배열 다시 숫자로 변환.
    public static int arrToInt(int[] numbers, int len) {
        int result = 0;
        for (int i = len - 1; i >= 0; i--) {
            result = result * 10 + numbers[i];
        }
        return result;
    }
 
    // 위치 바꾸는 함수
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
 

에잉 귀차나

 

먼저 숫자를 %10으로 자릿수를 배열로 담아준다.

 

조작 횟수가 길이보다 많다면 의미가 없어지므로 불필요한 연산은 줄여주었고,

 

재귀 dfs 함수와, 위치를 바꾸는 swap 함수, 배열을 숫자로 만드는 함수 arrToInt를 만들어 주었다.

 

재귀는 사이클이 없도록 if문에 조작 횟수를 다 사용했을 경우 return 하도록 구성했다.

 

for문을 통해 모든 경우의 수를 찾는다.

조작 횟수 내에 모든 수를 바꾸기 위해 swap 함수로 숫자 위치를 교환해 준다.

 

 

DFS 함수내에 재귀함수로 조작 횟수(cnt-1)를 1 줄이고 반복한다.

이후 swap을 다시 실행하여 원래 위치로 돌려준다. -> 일반적인 재귀 방법

 

 

조작 횟수가 조건대로 다 사용했다면, 배열을 숫자로 바꾸고, result와 비교하여 더 크다면 값을 넣어준다.

결국 조작 횟수 내로 모든 경우의 수를 다 실행한 후, 최댓값을 찾아준다.

\