[SWEA 1244번] 최대 상금

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

SW Expert Academy

 

DFS

import java.io.*;
import java.util.*;

public class Solution {

    static int N;

    static char[] num;

    static String result;

    static int length;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test < T + 1; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String input = st.nextToken();
            N = Integer.parseInt(st.nextToken());
            length = input.length();

            num = input.toCharArray();
            result = "";
            solution(0,0);
            System.out.println("#" + test + " " + result);
        }
    }

    private static void solution(int depth, int count) {
        if (count == N) {
            String current = new String(num);
            if(current.compareTo(result) > 0){
                result = current;
            }
            return;
        }

        for (int i = depth; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                swap(i, j);
                solution(i,count+1);
                swap(i, j);
            }
        }
    }

    private static void swap(int front, int back) {
        char temp = 0;
        temp = num[front];
        num[front] = num[back];
        num[back] = temp;
    }
}

 

SET + DFS

import java.io.*;
import java.util.*;

public class Solution {
    static int N;
    static char[] num;
    static String result;
    static int length;

    static Set<String>[] visited; // 깊이에 따른 방문 상태 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test <= T; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String input = st.nextToken();
            N = Integer.parseInt(st.nextToken());

            num = input.toCharArray();
            length = num.length;
            result = "0";

            visited = new HashSet[N + 1]; // 깊이마다 Set 초기화
            for (int i = 0; i <= N; i++) {
                visited[i] = new HashSet<>();
            }

            solution(0,0);

            System.out.println("#" + test + " " + result);
        }
    }

    private static void solution(int depth,int count) {
        String current = new String(num);
        if (visited[count].contains(current)) return;
        visited[count].add(current);

        if (count == N) {
            if (current.compareTo(result) > 0) {
                result = current;
            }
            return;
        }

        for (int i = depth; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                swap(i, j);
                solution(i,count + 1);
                swap(i, j); // backtracking
            }
        }
    }

    private static void swap(int i, int j) {
        char tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }
}

 

 

6개월 전에 풀었던 문제를 다시 도전해보았다. 처음에는 문제를 제대로 해결했다고 생각했지만, 테스트 케이스가 부족했던 탓에 기존 코드에 오류가 있었다는 것을 뒤늦게 알게 되었다.

 

 

 

그래서 이번에는 이전과 동일하게 DFS 방식으로 다시 풀었고, 처음 제출한 코드는 위 사진과 같이 무려 4153ms가 걸릴 정도로 비효율적이었다.

 

이를 개선하기 위해 중복 상태를 줄이는 가지치기 기법을 도입했고, 그 핵심은 Set을 이용한 중복 방지였다.

특히 숫자의 길이가 2이고 교환 횟수가 10번처럼 클 경우, 각 깊이마다 Set 배열을 따로 두어 이미 방문한 상태는 다시 탐색하지 않도록 설계했다. 덕분에 시간 복잡도를 획기적으로 줄일 수 있었다.

if (current.compareTo(result) > 0) {
    result = current;
}

 

 

참고로 if (current.compareTo(result) > 0)는 문자열을 사전순으로 비교하는 구문인데,

• 결과가 양수면 current가 result보다 크다는 뜻이고
• 0이면 두 문자열이 같다는 의미이며
• 음수면 current가 더 작다는 의미다.

이번 기회에 문제를 더 깊이 이해할 수 있었고, 가지치기의 중요성도 다시 한번 느꼈다.