[JAVA]N으로 만들기(Baekjoon)

문제

문제

 준하는 노트에 수를 적다가 수가 만들어지는 방식을 깨달았다.

 처음에 어떤 숫자 하나를 적고 만들어진 수의 왼쪽이나 오른쪽에 숫자를 계속 붙이면 어떤 수 N이든 만들 수 있다는 것이다.

 다시 말해 어떤 수 N을 만들기 위해서는, 처음에 어떤 숫자를 하나 적고 아래의 두 가지 행동을 반복한다.

1. 수의 왼쪽에 숫자를 하나 적는다.
2. 수의 오른쪽에 숫자를 하나 적는다.

 준하는 어떤 수 N을 만드는 방법의 수가 몇 가지인지 궁금해졌다. 이를 알아내는 프로그램을 작성해주자. 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다.

 단, 숫자를 적는 과정에서 수는 0으로 시작할 수 있다.

입력

음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000)

출력

N을 만드는 방법의 수를 출력한다.

예제 입력 1

521

예제 출력 1

4

521을 만드는 방법은 다음과 같이 4가지이다.

• 1 → 21 → 521
• 2 → 21 → 521
• 2 → 52 → 521
• 5 → 52 → 521

예제 입력 2

9111

예제 출력 2

4

9111을 만드는 방법은 다음과 같이 4가지이다.

• 1 → 11 → 111 → 9111
• 1 → 11 → 911 → 9111
• 1 → 91 → 911 → 9111
• 9 → 91 → 911 → 9111

풀이

 이 문제는 트리 구조가 떠올랐다. 처음 시작점에서 좌 혹은 우로 문자열을 붙여 나가기 때문이다. 그렇게 문자열을 붙여나가는 과정을 문자열로 저장을 하고 Set에 add한다. 동일한 과정이라면 동일한 문자열을 가지고 세트를 사용하기 때문에 중복되는 것은 제외된다.

import java.util.Set;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.util.HashSet;
import java.io.InputStreamReader;

public class _17255 {
    static char[] arr;
    static Set<String> set;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = st.nextToken().toCharArray(); //입력을 char배열로 변환
        set = new HashSet<>();
        for(int i=0; i<arr.length; i++) {
            dfs(i,i, ""+arr[i], ""+arr[i]);
        }
        System.out.println(set.size());
    }

    //문자열을 다 만드는 과정이기에 dfs사용
    static void dfs(int L, int R, String s, String path) {
        //입력 문자의 모든 수들이 path변수에 포함됨
        if(L==0 && R==arr.length-1) {
            set.add(path);
            return;
        }
        //왼쪽 문자가 존재
        if(L-1>=0) {
            dfs(L-1, R, arr[L-1]+s, path+" "+arr[L-1]+s);
        }
        //오른쪽 문자가 존재
        if(R+1<arr.length) {
            dfs(L, R+1, s+arr[R+1], path+" "+s+arr[R+1]);
        }
    }
}