백준 17255 N으로 만들기 java


1. N의 모든 자릿수를 시작점으로 DFS를 진행
2. 왼쪽이나 오른쪽으로 수를 늘려나간다.
3. 2번에서 dfs를 거칠 때마다 모든 경로를 *StringBuilder*를 활용해 기록해놓는다. 이후 StringBuilder에 적힌 과정을 Set에 저장한다. (중복된 과정 제거 위함)
4. set의 size가 답이다.

(2) JAVA CODE ☕


import java.util.*;
import java.io.*;
 // b 17255 N으로 만들기
public class Main {
    static char [] values;
    static int N;
    static HashSet<String> set = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        values = br.readLine().toCharArray();
        N = Integer.parseInt(String.valueOf(values));

        for(int i = 0; i < values.length; i++){
            dfs(i,i,String.valueOf(values[i]), new StringBuilder().append(values[i]));
        }        System.out.println(set.size());
    }     public static void dfs(int L, int R, String now, StringBuilder path){
        if(L == 0 && R == values.length-1) {
            set.add(path.toString());
            return;
        }        StringBuilder next = new StringBuilder();
        if(L-1 >= 0){
            StringBuilder newOne = new StringBuilder().append(path);
            next.append(values[L-1]).append(now);
            newOne.append("->").append(next);
            dfs(L-1, R, next.toString() ,newOne);

        }        next.setLength(0);
        if(R+1 < values.length){
            StringBuilder newOne = new StringBuilder().append(path);
            next.append(now).append(values[R+1]);
            newOne.append("->").append(next);
            dfs(L, R+1, next.toString(), newOne);
        }     }
     public static int findDigit(int v){
        if( v == 0) return 1;
        return (int)Math.log10(v) + 1;
     }
}