16719 : ZAOC - JAVA

https://www.acmicpc.net/problem/16719

 

재귀 문제입니다.

재귀 중 한 갈래인 백트래킹은 아닙니다. 해가 아닌것 같으면 다시 돌아가는 백트래킹의 성질과는 다르게 이 문제는 만족하는 해를 재귀 함수에서 정해놓고 가지를 뻗어가게끔 설계함이 옳다고 판단했습니다. 100자의 문자열을 백트래킹으로 살피면 시간 초과가 날수 있을거라 생각했기 때문입니다.

 

처음에는 백트래킹인줄 알고 그렇게 설계하고 있었으나, 문제를 다시 읽고 문자열의 길이가 100임을 알게 되었고, 입력된 문자열에서 서순이 앞에 위치한 문자를 찾고, 앞뒤로 분할정복을 돌리며 찾은 문자열들을 print 해주었고, 바로 맞을수 있었습니다.

 

소스코드

import java.util.*;
import java.io.*;
public class Main {
    static boolean[] check;
    static String s;
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        s = sc.nextLine();
        check = new boolean[s.length()];
        print(0, s.length()-1);
        bw.flush();
        bw.close();
        sc.close();
    }
    public static void print(int start, int end) throws IOException{
        //문자
        int comp = Integer.MAX_VALUE;
        //위치
        int index = -1;
        //최솟값 탐색
        for(int i = start; i <= end; i++){
            if(!check[i] && comp > s.charAt(i)){
                comp = s.charAt(i);
                index = i;
            }
        }
        if(comp == Integer.MAX_VALUE)
            return;

        check[index] = true;
        for(int i = 0; i < s.length(); i++){
            if(check[i]){
                bw.write(s.charAt(i));
            }
        }
        bw.write('\n');
        print(index + 1, end);
        print(start, index - 1);
    }
}