백준 10597번 : 순열장난

문제 : https://www.acmicpc.net/problem/10597

 

요소에 대한 모든 케이스를 하나씩 확인해 간다면 쉽게 정답을 향해 갈 수 있습니다. 심지어 친절하게도 수열의 형태가 다양한 경우 그중 아무거나 하나만 출력해도 됩니다. 

 

다만, 위 과정의 시간복잡도에 대해 생각을 해보니, 생각이 많아지기 시작했습니다. 우선 입력값을 보면..

 

-  N은 최대 50개의 수

-  1초

 

입력받는 값이 최대 50개의 수로 이뤄져있다는 것을 통해 문자열의 길이가 최대 9 +(50 - 9 ) * 2 = 91이라는 것을 알 수 있습니다. 

 

하지만 앞서 말한 "모든 케이스의 확인" 에 대해 저는 아래와 같이 생각을 했습니다. 

 

input : ... abc..(a, b, c <10)

a를 기준으로 수를 선택 할 수 있는 경우는 2가지 (a, a*10 + b) 

즉, Input 의 길이가 N 인 경우 : O(2^N) 

 

DP 문제가 아닐까 해서 그래서 풀이 방법의 최적화를 위해 고민을 했었습니다.

 

하지만 슬프게도 이 문제는 "모든 경우를 확인"이라는 포인트에서  "가능한 경우를 하나만 확인" 로 바꿔 생각해 본다면 시간복잡도에 크게 신경 쓰지 않아도 풀리는 문제였습니다. ㅠ

 

다시 위에 상황을 생각해봅시다.

input :... abc..(a, b, c <10)

a를 기준으로 수를 선택할 수 있는 경우는 2가지 (a, a*10 + b) 

즉, Input의 길이가 N 인 경우 : O(2^N) 

 

그렇다면 위와 같이 a를 기준으로 선택할 수 있는 경우가 2가지가 되는 경우가 가능한 경우를 생각해 보면 2가지의 조건이 있습니다. 

1. a*10 + b 가 수열 내 최대 수 보다 작아야 합니다.

2. a*10 + b 가 이미 나온 수가 아니여야 합니다. 

 

 또한, 앞서 조건에서 언급한 것과 같이, 정답이 가능 한 하나의 수열만 확인하면 됩니다. 이는 즉 가능한 경우를 발견한다면 더 이상 탐색을 진행할 필요가 없다는 것입니다. 

 

따라서 이 문제를 백트래킹으로 푸는 과정이 이론적으로 O(2^N)으로 예상되어도, 문제를 해결하는데 지장이 없습니다.

+ 좀 더 수학적인 증거를 보여드리고 싶었지만.. 저의 배움이 부족하여 느낌적인 느낌으로 호소하게 되었습니다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Num10597순열장난 {
    static String input;
    static int n;
    static boolean[] num;
    static String answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
        n = (input.length() + 9) / 2;
        num = new boolean[n + 1];
        dp(0, new ArrayList<>());
        System.out.println(answer);
    }

    public static void dp(int index, List<Integer> list) {
        if (index == input.length()) {
            StringBuilder sb = new StringBuilder();
            for (int now : list) {
                sb.append(now).append(" ");
            }
            answer = sb.toString();
            return;
        }

        int num1 = Character.getNumericValue(input.charAt(index));
        if (num1 <= n && !num[num1]) {
            list.add(num1);
            num[num1] = true;
            dp(index + 1, list);
            if (answer != null) return; // 정답이 발견된 경우 조기 종료
            list.remove(list.size() - 1);
            num[num1] = false;
        }

        if (index + 1 < input.length()) {
            num1 = (Character.getNumericValue(input.charAt(index)) * 10) + Character.getNumericValue(input.charAt(index + 1));
            if (num1 <= n && !num[num1]) {
                list.add(num1);
                num[num1] = true;
                dp(index + 2, list);
                if (answer != null) return; // 정답이 발견된 경우 조기 종료
                list.remove(list.size() - 1);
                num[num1] = false;
            }
        }
    }
}

 

 

+ DP와 백트래킹

 

"DP와 백트래킹 문제를 어떻게 구분할 수 있을까?"에 대해 고민이 되기 시작했습니다. 위 문제를 고민하며 나온 나름의 결론은 

 

- 가능한 정답을 찾는 문제 : 백트래킹 쪽으로 생각

- 가능한 정답 가운데 최적의 정답을 찾는 문제 : DP로 생각

 

단순하게 예를 들어 위 문제가 "가능한 수열 중 가장 특정 기준에 부합한(오름차순.. 등) 수열 하나를 출력하세요"로 변경된다면 DP 쪽으로 생각을 먼저 해보도록 하자 라는 저만의 규칙을 하나 만들었습니다. 그럼 안녕.