[백준] 17255: N으로 만들기 - JAVA

in Algorithm on 자료 구조

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

풀이

어떤 수 N을 만들어야 하는데 두 가지 행동을 반복해서 만들어야 한다.

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

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

따라서, 숫자 N을 입력받을때 char 배열로 받아서 인덱스로 탐색하면서

시작위치를 정하고 dfs탐색을 했다.

left와 right 인덱스를 기억하면서 left가 0, right가 길이-1이 되면 set자료구조에 넣었다.

나온 수를 순서대로 string으로 만들어 set자료구조에 넣었기 때문에 중복된 것이 제외되고

set의 size를 출력하면 경우의 수가 된다.

메모리: 17296KB

시간: 216ms

언어: Java 11

코드

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

public class Main {
    static char[] arr;
    static Set<String> set;

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

        set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            dfs(i, i, "" + arr[i], "" + arr[i]);
        }

        System.out.println(set.size());
    }

    private static void dfs(int left, int right, String now, String str) {
        if (left == 0 && right == arr.length - 1) {
            set.add(str);
        }

        if (left > 0) {
            dfs(left - 1, right, arr[left - 1] + now, str + " " + arr[left - 1] + now);
        }

        if (right < arr.length - 1) {
            dfs(left, right + 1, now + arr[right + 1], str + " " + now + arr[right + 1]);
        }
    }

}